RIAIL: An Index Method for Reachability Query in Large Scale Graphs
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [15]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Graph has been widely used to model the applications in social network, semantic web, computational biology and software analysis. Reachability query is one kind of basic queries in graph data. Currently, in allusion to graph, several index algorithms have been proposed to answer reachability query, however, they can not scale to large graph flexibly. To address the issue, a new index method called RIAIL (reachability index augmented by interval labeling) is developed in this paper. RIAIL labels each node with four-tuple. The first two elements are interval labels that encode reachability information of the spanning tree, and the last two elements encode reachability information of non-tree edges. RIAIL only needs to index when querying and the cost of index construction is little. Finally, a wide range of experiments on real and synthetic datasets are conducted to demonstrate that RIAIL can efficiently handle reachability query and easily scale to large graph.

    Reference
    [1] Aggarwal CC, Wang H. Managing and Mining Graph Data. Heidelberg: Springer-Verlag, 2010.
    [2] Cormen TH, Leiserson CE, Rivest RL, et al. Introduction to Algorithms. 3rd ed., Cambridge: The MIT Press, 2009.
    [3] Agrawal R, Borgida A, Jagadish HV. Efficient management of transitive relationships in large data and knowledge bases. In: Proc. of the 1989 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM Press, 1989. 253-262.
    [4] Cohen E, Halperin E, Kaplan H, et al. Reachability and distance queries via 2-hop labels. In: Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: ACM Press, 2002. 937-946.
    [5] Wang H, He H, Yang J, et al. Dual labeling: Answering graph reachability queries in constant time. In: Proc. of the 22nd Int'l Conf. on Data Engineering. Washington: IEEE, 2006. 75-75.
    [6] Cheng J, Yu J X, Lin X, et al. Fast computation of reachability labeling for large graphs. In: Proc. of the 10th Int'l Conf. on Advances in Database Technology. Berlin, Heidelberg: Springer-Verlag, 2006. 961-979.
    [7] Cheng J, Yu J X, Lin X, et al. Fast computing reachability labelings for large graphs with high compression rate. In: Proc. of the 11th Int'l Conf. on Extending Database Technology: Advances in Database Technology. New York: ACM Press, 2008. 193-204.
    [8] Jin R, Xiang Y, Ruan N, et al. 3-hop: A high-compression indexing scheme for reachability query. In: Proc. of the 2009 ACM SIGMOD Int'l Conf. on Management of data. New York: ACM Press, 2009. 813-826.
    [9] Trißl S, Leser U. Fast and practical indexing and querying of very large graphs. In: Proc. of the 2007 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM Press, 2007. 845-856.
    [10] Jin R, Xiang Y, Ruan N, et al. Efficiently answering reachability queries on very large directed graphs. In: Proc. of the 2008 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM Press, 2008. 595-608.
    [11] Yildirim H, Chaoji V, Zaki MJ. Grail: Scalable reachability index for large graphs. Proc. of the VLDB Endowment, 2010,3(1-2): 276-284.
    [12] Zhang Z, Yu J X, Qin L, et al. I/O cost minimization: reachability queries processing over massive graphs. In: Proc. of the 15th Int'l Conf. on Extending Database Technology. New York: ACM Press, 2012. 468-479.
    [13] Yıldırım H, Chaoji V, Zaki MJ. GRAIL: A scalable index for reachability queries in very large graphs. The VLDB Journal—The Int'l Journal on Very Large Data Bases, 2012,21(4):509-534.
    [14] Seufert S, Anand A, Bedathur S, et al. Ferrari: Flexible and efficient reachability range assignment for graph indexing. In: Proc. of the 2013 IEEE Int'l Conf. on Data Engineering. Washington: IEEE, 2013. 1009-1020.
    [15] Dietz PF. Maintaining order in a linked list. In: Proc. of the 14th annual ACM Symp. on Theory of Computing. New York: ACM Press, 1982. 122-127.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

解宁,申德荣,冯朔,寇月,聂铁铮,于戈. RIAIL:大规模图上的可达性查询索引方法.软件学报,2014,25(S2):213-224

Copy
Share
Article Metrics
  • Abstract:2823
  • PDF: 4732
  • HTML: 0
  • Cited by: 0
History
  • Received:May 07,2014
  • Revised:August 19,2014
  • Online: January 29,2015
You are the first2038312Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063