research-article

On incremental maintenance of 2-hop labeling of graphs

Authors:

Ramadhana Bramandia,

Wee Keong NgAuthors Info & Claims

WWW '08: Proceedings of the 17th international conference on World Wide Web

Pages 845 - 854

https://doi.org/10.1145/1367497.1367611

Published: 21 April 2008 Publication History

Abstract

Recent interests on XML, 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 large collections 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 Web data changes over time. In response to these, this paper studies the incremental maintenance of 2-hop labeling. We identify the main reason for the inefficiency of updates of existing 2-hop labels. We propose two updatable 2-hop labelings, hybrids of 2-hop labeling, and their incremental maintenance algorithms. The proposed 2-hop labeling is derived from graph connectivities, as opposed to set cover which is used by all previous work. Our experimental evaluation illustrates the space efficiency and update performance of various kinds of 2-hop labeling. The main conclusion is that there is a natural way to spare some index size for update performance in 2-hop labeling.

References

[1]

R. Agrawal and H. V. Jagadish. Hybrid transitive closure algorithms. In The VLDB Journal, pages 326--334, 1990.

Digital Library

[2]

R. Bar-Yehuda and D. Rawitz. Approximating element-weighted vertex deletion problems for the complete k-partite property. J. Algorithms, 42(1):20--40, 2002.

Digital Library

[3]

V. Batagelj and A. Mrvar. Pajek datasets, 2006.http://vlado.fmf.uni-lj.si/pub/networks/data/.

[4]

R. Bramandia, J. Cheng, B. Choi, and J. X. Yu. Optimizing updates of recursive xml views of relations. (Technical report at http://www.ntu.edu.sg/home/kkchoi/techreport.pdf).

[5]

J. Cheng, Y. Ke, W. Ng, and A. Lu. Fg-index: towards verification-free query processing on graph databases. In SIGMOD, pages 857--872, 2007.

Digital Library

[6]

J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. Yu. Fast computing reachability labelings for large graphs with high compression rate. In EDBT, 2008.

Digital Library

[7]

J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computation of reachability labeling for large graphs. In EDBT, pages 961--979, 2006.

Digital Library

[8]

J. Cheng, J. X. Yu, and N. Tang. Fast reachability query processing. In DASFAA, pages 674--688, 2006.

Digital Library

[9]

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5):1338--1355, 2003.

Digital Library

[10]

E. Cohen, H. Kaplan, and T. Milo. Labeling dynamic xml trees. In PODS, pages 271--281, 2002.

Digital Library

[11]

European Bioinformatics Institute. QuickGo: GO browser. Web interface. http://www.ebi.ac.uk/ego/.

[12]

H. Jiang, H. Lu, W. Wang, and B. Ooi. Xr-tree: Indexing xml data for efficient structural join. In ICDE, 2003.

[13]

R. Johnsonbaugh and M. Kalin. A graph generation software package. In SIGCSE, pages 151--154, 1991.

Digital Library

[14]

Karypis lab. Family of Multilevel Partitioning Algorithms. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.

[15]

B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. In Bell Systems Technical Journal, pages 291--308, 1970.

[16]

J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632, 1999.

Digital Library

[17]

J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, pages 177--187, 2005.

Digital Library

[18]

G. Miklau. UW XML repository. http://www.cs.washington.edu/research/xmldatasets/.

[19]

R. Peeters. The maximum edge biclique problem is np-complete. Discrete Appl. Math., 131(3):651--654, 2003.

Digital Library

[20]

R. Schenkel, A. Theobald, and G. Weikum. Hopi: An efficient connection index for complex xml document collections. In EDBT, pages 237--255, 2004.

[21]

R. Schenkel, A. Theobald, and G. Weikum. Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In ICDE, pages 360--371, 2005.

Digital Library

[22]

S. Trißl and U. Leser. Fast and practical indexing and querying of very large graphs. In SIGMOD, pages 845--856, 2007.

Digital Library

[23]

W3C. Resource description framework (rdf). http://www.w3.org/RDF.

[24]

W3C. Semantic web activity. http://www.w3.org/2001/sw/.

[25]

G. Wu, K. Zhang, C. Liu, and J.-Z. Li. Adapting prime number labeling scheme for directed acyclic graphs. In DASFAA, pages 787--796, 2006.

Digital Library

[26]

X. Wu, M. L. Lee, and W. Hsu. A prime number labeling scheme for dynamic ordered xml trees. In ICDE, pages 66--78, 2004.

Digital Library

[27]

X. Yan, P. S. Yu, and J. Han. Graph indexing based on discriminative frequent structure analysis. ACM Trans. Database Syst., 30(4):960--993, 2005.

Digital Library

[28]

X. Yan, F. Zhu, P. S. Yu, and J. Han. Feature-based similarity search in graph structures. ACM Trans. Database Syst., 31(4):1418--1453, 2006.

Digital Library

[29]

C. Zhang, J. F. Naughton, D. J. DeWitt, Q. Luo, and G. M. Lohman. On supporting containment queries in relational database management systems. In SIGMOD, 2001.

Digital Library

Cited By

Yu CRen TLi WLiu HMa HZhao Y(2024)BL: An Efficient Index for Reachability Queries on Large GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.332721510:2(108-121)Online publication date: Apr-2024
https://doi.org/10.1109/TBDATA.2023.3327215
Byun J(2022)Enabling Time-Centric Computation for Efficient Temporal Graph Traversals From Multiple SourcesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.300567234:4(1751-1762)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.3005672
Wen DYang BZhang YQin LCheng DZhang W(2021)Span-reachability querying in large temporal graphsThe VLDB Journal10.1007/s00778-021-00715-z31:4(629-647)Online publication date: 23-Nov-2021
https://doi.org/10.1007/s00778-021-00715-z
Show More Cited By

Index Terms

On incremental maintenance of 2-hop labeling of graphs

Recommendations

3-HOP: a high-compression indexing scheme for reachability query
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data

Reachability queries on large directed graphs have attracted much attention recently. The existing work either uses spanning structures, such as chains or trees, to compress the complete transitive closure, or utilizes the 2-hop strategy to describe the ...
Fully Dynamic 2-Hop Cover Labeling
Special Issue ESA 2016, Regular Papers and Special Issue SEA 2018

The 2-hop Cover labeling of a graph is currently the best data structure for answering shortest-path distance queries on large-scale networks, since it combines low query times, affordable space occupancy, and reasonable preprocessing effort. Its main ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '08: Proceedings of the 17th international conference on World Wide Web

April 2008

1326 pages

ISBN:9781605580852

DOI:10.1145/1367497

General Chairs:
Jinpeng Huai
Beihang University, China
,
Robin Chen
AT&T Labs, USA
,
Hsiao-Wuen Hon
Microsoft Research Asia, China
,
Yunhao Liu
HK University of Science and Technology, Hong Kong
,
Program Chairs:
Wei-Ying Ma
Microsoft Research Asia, China
,
Andrew Tomkins
Yahoo! Research, USA
,
Xiaodong Zhang
The Ohio State University, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 April 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '08

Sponsor:

ACM

WWW '08: The 17th International World Wide Web Conference

April 21 - 25, 2008

Beijing, China

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
371
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu CRen TLi WLiu HMa HZhao Y(2024)BL: An Efficient Index for Reachability Queries on Large GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.332721510:2(108-121)Online publication date: Apr-2024
Byun J(2022)Enabling Time-Centric Computation for Efficient Temporal Graph Traversals From Multiple SourcesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.300567234:4(1751-1762)Online publication date: 1-Apr-2022
Wen DYang BZhang YQin LCheng DZhang W(2021)Span-reachability querying in large temporal graphsThe VLDB Journal10.1007/s00778-021-00715-z31:4(629-647)Online publication date: 23-Nov-2021
Wen DHuang YZhang YQin LZhang WLin X(2020)Efficiently Answering Span-Reachability Queries in Large Temporal Graphs2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00104(1153-1164)Online publication date: Apr-2020
Raghebi ZBanaei-Kashani F(2018)Reach Me If You CanProceedings of the Fifth International ACM SIGMOD Workshop on Managing and Mining Enriched Geo-Spatial Data10.1145/3210272.3210276(19-24)Online publication date: 10-Jun-2018
Fan WHu CTian CChirkova RYang JSuciu D(2017)Incremental Graph ComputationsProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3035944(155-169)Online publication date: 9-May-2017
Wu GDing YLi YBao JZheng YLuo J(2017)Mining Spatio-Temporal Reachable Regions over Massive Trajectory Data2017 IEEE 33rd International Conference on Data Engineering (ICDE)10.1109/ICDE.2017.171(1283-1294)Online publication date: Apr-2017
Wu HHuang YCheng JLi JKe Y(2016)Reachability and time-based path queries in temporal graphs2016 IEEE 32nd International Conference on Data Engineering (ICDE)10.1109/ICDE.2016.7498236(145-156)Online publication date: May-2016
Jiang MFu AWong RSellis TDavidson SIves Z(2015)Exact Top-k Nearest Keyword Search in Large NetworksProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2749447(393-404)Online publication date: 27-May-2015
Sellis TDavidson SIves Z(2015)Proceedings of the 2015 ACM SIGMOD International Conference on Management of DataundefinedOnline publication date: 27-May-2015
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents