Computer Science ›› 2018, Vol. 45 ›› Issue (3): 178-181.doi: 10.11896/j.issn.1002-137X.2018.03.028

Previous Articles     Next Articles

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

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   
No Suggested Reading articles found!