Incremental Maintenance of 2-Hop Labeling of Large Graphs

Recent interests on XML, the Semantic Web, and Web ontology, among other topics, have sparked a renewed interest on graph-structured databases. A fundamental query on graphs is the reachability test of nodes. Recently, 2-hop labeling has been proposed to index a large collection of XML and/or graphs...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2010-05, Vol.22 (5), p.682-698
Main Authors: Bramandia, R., Choi, B., Wee Keong Ng
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Collection
Computer science
control theory
systems
Computer Society
Computer systems and distributed systems. User interface
Database languages
Exact sciences and technology
Extensible Markup Language
Graphs
Indexing
Indexing methods
Information retrieval. Graph
Information systems. Data bases
Labeling
Maintenance
Marking
Memory organisation. Data processing
Ontologies
OWL
query processing
Resource description framework
Semantic Web
Semantics
Software
Speech and sound recognition and synthesis. Linguistics
Studies
Testing
Theoretical computing
XML
XML/XSL/RDF
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent interests on XML, the Semantic Web, and Web ontology, among other topics, have sparked a renewed interest on graph-structured databases. A fundamental query on graphs is the reachability test of nodes. Recently, 2-hop labeling has been proposed to index a large collection of XML and/or graphs for efficient reachability tests. However, there has been few work on updates of 2-hop labeling. This is compounded by the fact that data may often change over time. In response to these, this paper studies incremental maintenance of 2-hop labeling. We identify the main reason for the inefficiency of updates of existing 2-hop labels. We propose three updatable 2-hop labelings, hybrids of 2-hop labeling, and their incremental maintenance algorithms. The proposed 2-hop labeling is derived from graph connectivity, as opposed to set cover which is used by most previous works. Our experimental evaluation illustrates the space efficiency and update performance of various kinds of 2-hop labelings. Our results show that our incremental maintenance algorithm can be two orders of magnitude faster than previous methods and the size of our 2-hop labeling can be comparable to existing 2-hop labeling. We conclude that there is a natural way to spare some index size for update performance in 2-hop labeling.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2009.117