Computer Science ›› 2024, Vol. 51 ›› Issue (6A): 230500031-10.doi: 10.11896/jsjkx.230500031
• Big Data & Data Science • Previous Articles Next Articles
TONG Zhengnan, BU Tianming
CLC Number:
| [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. |
| [1] | DU Ming, XING Rui-ping, ZHOU Jun-feng, TAN Yu-ting. k-step Reachability Query Processing on Label-constrained Graph [J]. Computer Science, 2022, 49(12): 283-292. |
|
||
Home