| 基于双向双区间标签实现k步可达性查询 |
| |
| 引用本文： | 宋亚青,武优西,刘靖宇,李艳.基于双向双区间标签实现k步可达性查询[J].计算机科学,2018,45(3):178-181. |
| |
| 作者姓名： | 宋亚青 武优西 刘靖宇 李艳 |
| |
| 作者单位： | 河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学经济管理学院 天津300401 |
| |
| 基金项目： | 本文受国家自然科学基金(61673159),河北省自然科学基金(F2016202145),黑龙江省自然科学基金(F2017019),河北省科技计划项目(15210325),河北省教育厅青年基金(QN2014192)资助 |
| |
| 摘 要： | 近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。 实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。
|
| 关 键 词： | k步可达性查询 不同分支 双向 双区间 |
| 收稿时间： | 2016/12/6 0:00:00 |
| 修稿时间： | 2017/4/15 0:00:00 |
k-step Reachability Queries Based on Bidirectional Double Interval Labeling Indexes |
| |
| SONG Ya-qing,WU You-xi,LIU Jing-yu and LI Yan.k-step Reachability Queries Based on Bidirectional Double Interval Labeling Indexes[J].Computer Science,2018,45(3):178-181. |
| |
| Authors: | SONG Ya-qing WU You-xi LIU Jing-yu and LI Yan |
| |
| Affiliation: | School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401,China,School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401,China,School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401,China and School of Economics and Management,Hebei University of Technology,Tianjin 300401,China |
| |
| Abstract: | 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. |
| |
| Keywords: | Reachability queries within k steps Different branches Bidirectional Double interval |
|
|
点击此处可从《计算机科学》下载全文 |
|
