计算机科学 ›› 2024, Vol. 51 ›› Issue (6A): 230500031-10.doi: 10.11896/jsjkx.230500031
同正南, 卜天明
TONG Zhengnan, BU Tianming
摘要： k步可达查询用于在给定的有向无环图(Directed Acyclic Graph,DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出了一种构建在大图上的基于树覆盖的倍增索引来提高索引查询效率,并结合GRAIL算法和改进的 FELINE 算法对本身就不可达查询点对进行剪枝。基于 19 个真实的数据集进行了实验测试,并将所提算法与现有算法在构建索引大小、索引时间、查询时间3个指标上进行了实验对比。实验结果验证了所提算法的高效性。
中图分类号:
| [1]FU L Z,MENG X F.Reachability indexing for large-scale-graphs:studies andforecasts[J].Journal of Computer Research and Development,2015,52(1):14. [2]ZHANG Y,LIU Y B,XIONG G,et al.Survey on Succinct Representation of Graph Data[J].Journal of Software,2014,25(9):16. [3]DING Y,ZHANG Y,LI Z H,et al.Research and advances on graph data mining[J].Journal of Computer Applications,2012,32(1):9. [4]WEISS M A.Data structures and algorithm analysis in C[M].[S.1].Benjamin/Cummings,1993. [5]STANN F,HEIDEMANN J.Rmst:Reliable data transport insensor networks[C]//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications,2003.IEEE,2003:102-112. [6]TAKUYA A,YOICHI I,YUICHI Y.Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C]//SIGMOD Conference.ACM,2013:349-360. [7]CHENG J,SHANG Z,CHENG H,et al.Efficient processing of k-hop reachability queries[J].VLDB J,2014,23(2):227-252. [8]COHEN E,HALPERIN E,KAPLAN H,et al.Reachability and distance queries via 2-hop labels[C]//Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms.ACM/SIAM,2002:937-946. [9]KING V.Fully dynamic algorithms for maintaining all-pairsshortest paths and transitive closure in digraphs[C]//40th Annual Symposium on Foundations of Computer Science(FOCS ’99).IEEE Computer Society,1999:81-91. [10]JIN R,WANG G.Simple,fast,and scalable reachability oracle[J].Proc.VLDB Endow.,2013,6(14):1978-1989. [11]CHENG J,HUANG S,WU H,et al.Tf-label:a topological-fol-ding labeling scheme for reachability querying in a large graph[C]//Proceedings of the ACM SIGMOD International Confe-rence on Management of Data(SIGMOD 2013).ACM,2013:193204. [12]ZHU A D,LIN W,WANG S,et al.Reachability queries on large dynamic graphs:a total order approach[C]//International Conference on Management of Data(SIGMOD 2014).ACM,2014:13231334. [13]AGRAWAL R,BORGIDA A,JAGADISH H V.Efficient ma-nagement of transitive relationships in large data and knowledge bases[C]//Proceedings of the 1989 ACM SIGMOD Interna-tional Conference on Management of Data.ACM,1989:253-262. [14]WANG H,HE H,YANG J,et al.Duallabeling:Answeringgraph reachability queries in constant time[C]//Proceedings of the 22nd International Conference on Data Engineering(ICDE 2006).IEEE Computer Society,2006:75. [15]TRISSL S,LESER U.Fast and practical indexing and querying of very large graphs[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.ACM,2007:845-856. [16]CHEN L,GUPTA A,KURUL M E.Stack based algorithms for pattern matching on dags[C]// Proceedings of the 31st International Conference on Very Large Data Bases.ACM,2005:493-504. [17]JIN R,XIANG Y,RUAN N,et al.3-hop:a high-compression indexing scheme for reachability query[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data(SIGMOD 2009).ACM,2009:813826. [18]JIN R,RUAN N,XIANG Y,et al.Path-tree:An efficient reacha-bility indexing scheme for large directed graphs[J].ACM Trans.Database Syst.,2011,36(1):7:1-7:44. [19]CAI J,POON C K.Path-hop:efficiently indexing large graphs for reachability queries[C]// Proceedings of the 19th ACM Conference on Information and Knowledge Management(CIKM 2010).ACM,2010:119-128. [20]YILDIRIM H,CHAOJI V,ZAKI M J.GRAIL:scalable reacha-bility index for large graphs[J].Proc.VLDB Endow.,2010,3(1):276-284. [21]VELOSO R R,CERF L,JR W M,et al.Reachability queries in very large graphs:A fast refined on line search approach[C]//Proceedings of the 17th International Conference on Extending Database Technology(EDBT 2014).2014:511-522. [22]SEUFERT S,ANAND A,BEDATHUR S J,et al.FERRARI:flexible and efficient reachability range assignment for graph indexing[C]//29th IEEE International Conference on Data Engineering(ICDE 2013).IEEE Computer Society,2013:1009-1020. [23]WEI H,YU J X,LU C,et al.Reachability querying:An independent permutation labeling approach[J].Proc.VLDB Endow.,2014,7(12):1191-1202. [24]JIN R,RUAN N,XIANG Y,et al.A highwaycentric labeling approach for answering distance queries on large sparse graphs[C]//Proceedings of the ACM SIGMOD International Confe-rence on Management of Data(SIGMOD 2012).USA,ACM,2012:445-456. [25]WONG T.Answering reachability queries on incrementally updated graphs by hierarchical labeling schema[J].J.Comput.Sci.Technol.,2016,31(2):381-399. |
|
||
首页