宋亚青,武优西,刘靖宇,李艳.基于双向双区间标签实现k步可达性查询[J].计算机科学,2018,45(3):178-181
基于双向双区间标签实现k步可达性查询
k-step Reachability Queries Based on Bidirectional Double Interval Labeling Indexes
投稿时间:2016-12-06  修订日期:2017-04-15
DOI:10.11896/j.issn.1002-137X.2018.03.028
中文关键词:  k步可达性查询,不同分支,双向,双区间
英文关键词:Reachability queries within k steps,Different branches,Bidirectional,Double interval
基金项目:本文受国家自然科学基金(61673159),河北省自然科学基金(F2016202145),黑龙江省自然科学基金(F2017019),河北省科技计划项目(15210325),河北省教育厅青年基金(QN2014192)资助
作者单位E-mail
宋亚青 河北工业大学计算机科学与软件学院 天津300401
河北省大数据重点实验室 天津300401 
1198853275@qq.com 
武优西 河北工业大学计算机科学与软件学院 天津300401
河北省大数据重点实验室 天津300401 
wuc567@163.com 
刘靖宇 河北工业大学计算机科学与软件学院 天津300401
河北省大数据重点实验室 天津300401 
 
李艳 河北工业大学经济管理学院 天津300401  
摘要点击次数: 480
全文下载次数: 298
中文摘要:
      近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。 实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。
英文摘要:
      Recently,reachability query is one of the main research topics on graph data.GRAIL can deal with k-step reachability queries efficiently,however,it is not suitable for processing the query in which the vertex pairs are located in different branches.This paper further proposed RE-GRAIL algorithm which employs a bidirectional double interval labeling indexes to tackle the problem.At last,five real datasets were employed to validate the performances of the proposed algorithm in terms of different metrics,including indexing time index size,query processing time and scalability.Experimental results show that RE-GRAIL has better performance than other competitive algorithms.
查看全文  查看/发表评论  下载PDF阅读器