Journal of Software:2014.25(S2):213-224

(东北大学 信息科学与工程学院, 辽宁 沈阳 110004)
RIAIL: An Index Method for Reachability Query in Large Scale Graphs
XIE Ning,SHEN De-Rong,FENG Shuo,KOU Yue,NIE Tie-Zheng,YU Ge
(College of Information Science and Engineering, Northeastern University, Shenyang 110004, China)
Chart / table
Similar Articles
Article :Browse 1273   Download 1493
Received:May 07, 2014    Revised:August 19, 2014
> 中文摘要: 图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.
中文关键词:   可达性查询  索引算法  区间标记  生成树
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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61033007,61472070);国家重点基础研究发展计划(973)(2012CB316201);教育部-英特尔信息技术专项科研基金(MOE-INTEL-2012-06) 国家自然科学基金(61033007,61472070);国家重点基础研究发展计划(973)(2012CB316201);教育部-英特尔信息技术专项科研基金(MOE-INTEL-2012-06)
Foundation items:
Reference text:


XIE Ning,SHEN De-Rong,FENG Shuo,KOU Yue,NIE Tie-Zheng,YU Ge.RIAIL: An Index Method for Reachability Query in Large Scale Graphs.Journal of Software,2014,25(S2):213-224