计算机科学 ›› 2018, Vol. 45 ›› Issue (3): 178-181.doi: 10.11896/j.issn.1002-137X.2018.03.028
宋亚青,武优西,刘靖宇,李艳
SONG Ya-qing, WU You-xi, LIU Jing-yu and LI Yan
摘要： 近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。 实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。
| [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! |
|
||
首页