TY - JOUR
T1 - Incremental maintenance of 2-Hop labeling of large graphs
AU - Bramandia, Ramadhana
AU - CHOI, Koon Kau
AU - Ng, Wee Keong
N1 - Funding Information:
The authors are very grateful to Jeffrey Xu Yu and Jiefeng Cheng for the implementation of 2-hop labelings [25], [7] used in [4]. The first and second authors are partially supported by the start-up grant from Nanyang Technological University and FRG/07-08/I-59 and GRF/HKBU210409 from Hong Kong Baptist University.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Indexing methods
KW - Query processing
KW - XML/XSL/RDF
UR - http://www.scopus.com/inward/record.url?scp=77949917433&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2009.117
DO - 10.1109/TKDE.2009.117
M3 - Article
AN - SCOPUS:77949917433
SN - 1041-4347
VL - 22
SP - 682
EP - 698
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 5
M1 - 4912201
ER -