%0 Journal Article
%T RIAIL:大规模图上的可达性查询索引方法
%A 于戈
%A 冯朔
%A 寇月
%A 申德荣
%A 聂铁铮
%A 解宁
%J -
%D 2014
%X 图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据
%K 图 可达性查询 索引算法 区间标记 生成树
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=14039&flag=1