We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 31 Issue 2
March  2016
Turn off MathJax
Article Contents
Abstract
References
Tak-Lam Wong. Answering Reachability Queries on Incrementally Updated Graphs by Hierarchical Labeling Schema[J]. Journal of Computer Science and Technology, 2016, 31(2): 381-399. DOI: 10.1007/s11390-016-1633-7
Citation: Tak-Lam Wong. Answering Reachability Queries on Incrementally Updated Graphs by Hierarchical Labeling Schema[J]. Journal of Computer Science and Technology, 2016, 31(2): 381-399. DOI: 10.1007/s11390-016-1633-7
shu

Answering Reachability Queries on Incrementally Updated Graphs by Hierarchical Labeling Schema

  • Department of Mathematics and Information Technology, The Hong Kong Institute of Education, Hong Kong, China

More Information
  • Author Bio:

    Tak-Lam Wong received his B.E., M.Phil., and Ph.D. degrees from The Chinese University of Hong Kong in 2001,2003, and 2006, respectively. He is currently an assistant professor of The Hong Kong Institute of Education. His research interests lie in the areas of Web mining, information extraction, machine learning, knowledge management, and e-Learning. He has published papers in a number of journals such as IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transactions on Knowledge and Data Engineering, and ACM Transactions on Information Systems.

  • Received Date: August 14, 2014
  • Revised Date: June 07, 2015
  • Published Date: March 04, 2016
    Abstract
  • We proposed a novel solution schema called the Hierarchical Labeling Schema (HLS) to answer reachability queries in directed graphs. Different from many existing approaches that focus on static directed acyclic graphs (DAGs), our schema focuses on directed cyclic graphs (DCGs) where vertices or arcs could be added to a graph incrementally. Unlike many of the traditional approaches, HLS does not require the graph to be acyclic in constructing its index. Therefore, it could, in fact, be applied to both DAGs and DCGs. When vertices or arcs are added to a graph, the HLS is capable of updating the index incrementally instead of re-computing the index from the scratch each time, making it more efficient than many other approaches in the practice. The basic idea of HLS is to create a tree for each vertex in a graph and link the trees together so that whenever two vertices are given, we can immediately know whether there is a path between them by referring to the appropriate trees. We conducted extensive experiments on both real-world datasets and synthesized datasets. We compared the performance of HLS, in terms of index construction time, query processing time and space consumption, with two state-of-the-art methodologies, the path-tree method and the 3-hop method. We also conducted simulations to model the situation when a graph is updated incrementally. The performance comparison of different algorithms against HLS on static graphs has also been studied. Our results show that HLS is highly competitive in the practice and is particularly useful in the cases where the graphs are updated frequently.
    • FullText(HTML)
    • References (37)
  • [1]
    Yan X, Yu P, Han J. Substructure similarity search in graph databases. In Proc. the 2005 ACM SIGMOD International Conference on Management of Data, June 2005, pp.766- 777.
    [2]
    Golumbic M. Algorithm Graph Theory and Perfect Graphs (2nd edition). Amsterdam, The Netherlands: North- Holland, 2004.
    [3]
    Tian Y, Hankins R, Patel J. Efficient aggregation for graph summarization. In Proc. the 2008 ACM SIGMOD Inter national Conference on Management of Data, June 2008, pp.567-580.
    [4]
    Jin R, Xiang Y, Ruan N, Wang H. Efficiently answering reachability queries on very large directed graphs. In Proc. the 2008 ACM SIGMOD International Conference on Management of Data, June 2008, pp.595-608.
    [5]
    Jin R, Xiang Y, Ruan N, Fuhry D. 3HOP: A highcompression indexing scheme for reachability query. In Proc. the 2009 SIGMOD International Conference on Management of Data, June 29-July 2, 2009, pp.813-826.
    [6]
    Wu Y, Huang H, Hao Z, Chen F. Local community detection using link similarity. Journal of Computer Science and Technology, 2012, 27(6): 1261-1268.
    [7]
    Zhang Q. Dynamic uncertain causality graph for knowledge representation and reasoning: Discrete DAG cases. Journal of Computer Science and Technology, 2012, 27(1): 1-23.
    [8]
    Pechsiri C, Piriyakul R. Explanation knowledge graph construction through causality extraction from texts. Journal of Computer Science and Technology, 2010, 25(5): 1055- 1070.
    [9]
    D'Ulizia A, Ferri F, Formica A, Grifoni P. Approximating geographical queries. Journal of Computer Science and Technology, 2009, 24(6): 1109-1124.
    [10]
    Sakr S, Al-Naymat G. Efficient relational techniques for processing graph queries. Journal of Computer Science and Technology, 2010, 25(6): 1237-1255.
    [11]
    Abed S, Mohamed O A, Al-Sammane G. An abstract reachability approach by combining HOL induction and multiway decision graphs. Journal of Computer Science and Technology, 2009, 24(1): 76-95.
    [12]
    Jagadish H. A compression technique to materialize transitive closure. ACM Transactions on Database Systems (TODS), 1990, 15(4): 558-598.
    [13]
    Chen Y, Chen Y. An efficient algorithm for answering graph reachability queries. In Proc. the 24th IEEE International Conference on Data Engineering, April 2008, pp.893-902.
    [14]
    Wang H, He H, Yang J, Yu P, Yu J. Dual labeling: Answering graph reachability queries in constant time. In Proc. the 22nd IEEE International Conference on Data Engineering, April 2006, pp.75:1-75:12.
    [15]
    Agrawal R, Borgida A, Jagadish H. Efficient management of transitive relationships in large data and knowledge bases. In Proc. the 1989 ACM SIGMOD International Conference on Management of Data, May 31-June 2, 1989, pp.253-262.
    [16]
    Chen L, Gupta A, Kurul M. Stack-based algorithms for pattern matching on DAGs. In Proc. the 31st International Conference on Very Large Data Bases, August 30- September 2, 2005, pp.493-504.
    [17]
    Dey S K, Jamil H. A hierarchical approach to reachability query answering in very large graph databases. In Proc. the 19th ACM International Conference on Information and Knowledge Management, Oct. 2010, pp.1377-1380.
    [18]
    Trißl S, Leser U. Fast and practical indexing and querying of very large graphs. In Proc. the 2007 ACM SIGMOD International Conference on Management of Data, June 2007, pp.845-856.
    [19]
    Cohen E, Halperin E, Kaplan H, Zwick U. Reachability and distance queries via 2-hop labels. In Proc. the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2002, pp.937-946.
    [20]
    Schenkel R, Theobald A, Weikum G. HOPI: An efficient connection index for complex XML document collections. In Proc. the 9th Advances in Database Technology-EDBT 2004, March 2004, pp.237-255.
    [21]
    Cheng J, Yu J, Lin X, Wang H, Yu P. Fast computation of reachability labeling for large graphs. In Proc. the 10th Advances in Database Technology-EDBT 2006, March 2006, pp.961-979.
    [22]
    Cheng J, Yu J, Lin X,Wang H, Yu P. Fast computing reachability labelings for large graphs with high compression rate. In Proc. the 11th International Conference on Extending Database Technology: Advances in Database Technology, March 2008, pp.193-204.
    [23]
    Demetrescu C, Italiano G F. Fully dynamic all pairs shortest paths with real edge weights. Journal of Computer and System Sciences, 2006, 72(5): 813-837.
    [24]
    Henzinger M R, King V. Fully dynamic biconnectivity and transitive closure. In Proc. the 36th Annual Symposium on Foundations of Computer Science, October 1995, pp.664- 672.
    [25]
    Roditty L. Decremental maintenance of strongly connected components. In Proc. the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2013, pp.1143-1150.
    [26]
    Roditty L, Zwick U. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In Proc. the 36th Annual ACM Symposium on Theory of Computing, June 2004, pp.184-191.
    [27]
    Bramandia R, Choi B, Ng W K. Incremental maintenance of 2-hop labeling of large graphs. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5): 682-698.
    [28]
    Schenkel R, Theobald A, Weikum G. Efficient creation and incremental maintenance of the HOPI index for complex XML document collections. In Proc. the 21st IEEE International Conference on Data Engineering, April 2005, pp.360-371.
    [29]
    Jin R, Ruan N, Xiang Y, Wang H. Path-tree: An efficient reachability indexing scheme for large directed graphs. ACM Transactions on Database Systems (TODS), 2011,36(1): 7:1-7:44.
    [30]
    Yildirim H, Chaoji V, Zaki M J. DAGGER: A scalable index for reachability queries in large dynamic graphs. http://arxiv.org/abs/1301.0977, Jan. 2016.
    [31]
    Zhu A D, Lin W, Wang S, Xiao X. Reachability queries on large dynamic graphs: A total order approach. In Proc. the 2014 ACM SIGMOD International Conference on Management of Data, June 2014, pp.1323-1334.
    [32]
    Krommidas I, Zaroliagis C. An experimental study of algorithms for fully dynamic transitive closure. Journal of Experimental Algorithmics (JEA), 2008, 12: 1.6:1-1.6:22.
    [33]
    Cheng J, Huang S, Wu H, Fu A W C. TF-label: A topological-folding labeling scheme for reachability querying in a large graph. In Proc. the 2013 ACM SIGMOD International Conference on Management of Data, June 2013, pp.193-204.
    [34]
    Jin R, Wang G. Simple, fast, and scalable reachability oracle. Proc. the VLDB Endowment, 2013, 6(14): 1978-1989.
    [35]
    Yano Y, Akiba T, Iwata Y, Yoshida Y. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In Proc. the 22nd ACM International Conference on Information and Knowledge Management, October 27-November 1,2013, pp.1601-1606.
    [36]
    Y?d?r?m H, Chaoji V, Zaki M J. GRAIL: A scalable index for reachability queries in very large graphs. The VLDB Journal, 2012, 21(4): 509-534.
    [37]
    Johnsonbaugh R, Kalin M. A graph generation software package. ACM SIGCSE Bulletin, 1991,23(1): 151-154.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (20) PDF downloads (960) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return