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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • 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
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 07,2014
  • Revised:August 19,2014
  • Adopted:
  • Online: January 29,2015
  • Published:
You are the firstVisitors
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