计算机科学 ›› 2018, Vol. 45 ›› Issue (3): 178-181.doi: 10.11896/j.issn.1002-137X.2018.03.028

• 软件与数据库技术 • 上一篇    下一篇

基于双向双区间标签实现k步可达性查询

宋亚青,武优西,刘靖宇,李艳   

  1. 河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学计算机科学与软件学院 天津300401;河北省大数据重点实验室 天津300401,河北工业大学经济管理学院 天津300401
  • 出版日期:2018-03-15 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(61673159),河北省自然科学基金(F2016202145),黑龙江省自然科学基金(F2017019),河北省科技计划项目(15210325),河北省教育厅青年基金(QN2014192)资助

k-step Reachability Queries Based on Bidirectional Double Interval Labeling Indexes

SONG Ya-qing, WU You-xi, LIU Jing-yu and LI Yan   

  • Online:2018-03-15 Published:2018-11-13

摘要: 近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。 实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。

关键词: k步可达性查询,不同分支,双向,双区间

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.

Key words: Reachability queries within k steps,Different branches,Bidirectional,Double interval

[1] JIANG H,ZHANG J,MA H,et al.Mining authorship characteristics in bug repositories[J].Science China Information Sciences,2017,60(1):1-16.
[2] YIN D,GAO H,ZOU ZN,et al.Reachability query in heterogeneous information networks[J].Journal of Computer Research and Development,2016,53(2):479-491.
[3] HAN Y J.Method for finding critical paths based on concurrent reachable marking graph with Tags [J].Computer Science,2016,43(11):121-125.(in Chinese) 韩耀军.基于带标记的并发可达标识图的关键路径的求解方法[J].计算机科学,2016,43(11):121-125.
[4] NIE L,JIANG H,REN Z,et al.Query expansion based oncrowd knowledge for code search[J].IEEE Transactions on Services Computing,2016,9(5):771-783.
[5] XUAN J,JIANG H,HU Y,et al.Towards effective bug triage with software data reduction techniques[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(1):264-280.
[6] HOU R,WU J G.Efficient reduction algorithms for directed acyclic graph [J].Computer Science,2015,42(7):78-84.(in Chinese) 侯睿,武继刚.有向无环图的高效归约算法[J].计算机科学,2015,42(7):78-84.
[7] JIANG J X,YI P P,CHOI B,et al.Privacy-preserving reach-ability query services for massive networks[C]∥ 25th ACM International Conference on Information and Knowledge Management.Indiana,USA,2016:145-154.
[8] COHEN E,HALPERIN,KAPLAN H,et al.Reachability and distance queries via 2-hop labels [C]∥Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics.New York,USA,2002:937-946.
[9] FU L Z,MENG X F.Reachability indexing for large-scalegraphs:studies and forecasts[J].Journal of Computer Research and Development,2015,52(1):116-129.(in Chinese) 富丽贞,孟小峰.大规模图数据可达性索引技术:现状与展望[J].计算机研究与发展,2015,52(1):116-129.
[10] YILDIRIM H,CHAOJI V,ZAKI M J.Grail:Scalable reachability index for large graphs[J].PVLDB Journal,2010,3(1):276-284.
[11] AKIBA T,IWATA Y,YOSHIDA Y.Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C]∥Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.New York,USA,2013:349-360.
[12] ZHOU J F,CHEN W,FEI C P,et al.BiRch:A bidirectionalsearch algorithm for k-step reachability queries [J].Journal on Communications,2015,16(8):50-60.(in Chinese) 周军锋,陈伟,费春苹,等.BiRch:一种处理k步可达性查询的双向搜索算法[J].通信学报,2015,16(8):50-60.
[13] LI Y,SUN L,ZHU H Z,et al.A nettree for simple paths with length constraint and longest path in directed acyclic graph [J].Chinese Journal of Computer,2012,35(10):2194-2203.(in Chinese) 李艳,孙乐,朱怀忠,等.网树求解有向无环图中具有长度约束的简单路径和最长路径问题[J].计算机学报,2012,35(10):2194-2203.
[14] LI Y,WU Y X,HUANG C P,et al.Nettree for maximum disjoint paths with length constraint in DAG [J].Journal on Communications,2015,36(8):38-49.(in Chinese) 李艳,武优西,黄春萍,等.网树求解有向无环图中具有长度约束的最大不相交路径 [J].通信学报,2015,36(8):38-49.
[15] WU Y,WANG L,REN J,et al.Mining sequential patterns with periodic wildcard gaps [J].Applied Intelligence,2014,41(1):99-116.
[16] WU Y,SHEN C,JIANG H,et al.Strict pattern matching under non-overlapping condition[J].Science China Information Scien-ces,2017,60(1):1-16.
[17] CHENG J,SHANG Z,CHENG H.K-reach:Who is in yoursmall world[J].PVLDB Journal,2012,5(11):1292-1303.
[18] CHENG J,SHANG Z,CHENG H.Efficient processing of k-hop reachability queries[J].VLDB Journal,2014,23(2):227-252.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .