Large Scale Dynamic Graph Version Management: Requirements, Technologies, and Challenges

doi:10.11871/jfdc.issn.2096-742X.2024.04.006

Abstract

Abstract:

[Objective] In the era of big data, from daily life and production to scientific research, a massive amount of dynamic graph data has been generated. Managing and analyzing this data can effectively assist people in process design, intelligent decision-making, and scientific research. [Coverage] This article used keywords such as dynamic graph, evolution graph, and version graph management to search on CNKI and Google Scholar, and collected dozens of relevant literature. This article classifies and summarizes relevant research literature based on three categories: data models, management systems, and mining analysis methods, and analyzes the current research status at home and abroad. [Results] A theoretical study was conducted on the spatial consumption of three mainstream storage strategies for dynamic graph data, and preliminary conclusions were obtained. Secondly, a deeper summary of existing dynamic graph query requirements was conducted from the perspective of sets. Finally, based on the number of classifications in the paper, it was found that current research on dynamic graphs focuses more on mining and analysis. [Limitations] The relevant literature collected in this article mainly includes attribute graphs, and RDF related literature has not been covered. [Conclusions] After analyzing the relevant requirements and technologies for large-scale dynamic graph version management, this article also proposes some challenges, including the high spatial inflation brought by multi version management of dynamic graphs, efficient random retrieval of specified versions, and precise characterization of evolution relationships between versions.

Key words: dynamic graph, version management, graph data

ZENG Chenglin, WANG Huajin, ZHU Xiaojie, SHEN Zhihong. Large Scale Dynamic Graph Version Management: Requirements, Technologies, and Challenges[J]. Frontiers of Data and Computing, 2024, 6(4): 77-86, https://cstr.cn/32002.14.jfdc.CN10-1649/TP.2024.04.006.

Figures/Tables 2

References 42

[1]	苗又山. 大规模动态演化图的存储与分析系统研究[D]. 中国科学技术大学, 2015.
[2]	DEBROUVIER A, PARODI E, PERAZZO M. A model and query language for temporal graph databases[J]. The VLDB Journal, 2021, 30(5): 825-858.
[3]	HUANG S, CHENG J, WU H. Temporal Graph Traversals: Definitions, Algorithms, and Applications[R]. CoRR, 2014.
[4]	WU H, CHENG J, HUANG S. Path problems in temporal graphs[J]. Proceedings of the Vldb Endowment, 2014, 7(9): 721-732.
[5]	WU H, CHENG J, KE Y. Efficient Algorithms for Temporal Path Computation[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(11):2927-2942.
[6]	WU H, CHENG J, LU Y. Core decomposition in large temporal graphs[C]// 2015 IEEE International Conference on Big Data (Big Data), IEEE, 2015: 649-658.
[7]	WU H, HUANG Y, CHENG J. Reachability and time-based path queries in temporal graphs[C]// 2016 IEEE 32nd International Conference on Data Engineering (ICDE), IEEE, 2016: 145-156.
[8]	YANG Y, YAN D, WU H. Diversified temporal subgraph pattern mining[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016: 1965-1974.
[9]	JAIN A, SAHNI S K. Algorithms for optimal min hop and foremost paths in interval temporal graphs[J]. Applied Network Science, 2022, 7(1): 60.
[10]	WU H, CHENG J, HUANG S. Path problems in temporal graphs[J]. Proceedings of the Vldb Endowment, 2014, 7(9): 721-732.
[11]	WEBBER J. A programmatic introduction to Neo4j[C]// Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity, 2012: 217-218.
[12]	DAS A, MITRA A, BHAGAT S N. Issues and Concepts of Graph Database and a Comparative Analysis on list of Graph Database tools[C]// 2020 International Conference on Computer Communication and Informatics (ICCCI), IEEE, 2020: 1-6.
[13]	GUAY PAZ J R. Introduction to azure cosmos db[C]// Microsoft Azure Cosmos DB Revealed: A Multi-Model Database Designed for the Cloud, 2018: 1-23.
[14]	VANDER LANS R F. InfiniteGraph:Extending Business, Social and Government Intelligence with Graph Analytics[R]. Technical report, 20, 2010.
[15]	CARROLL J J, DICKINSON I, DOLLIN C. Jena: implementing the semantic web recommendations[C]// Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, 2004: 74-83.
[16]	ERLING O, MIKHAILOV I. RDF Support in the Virtuoso DBMS[M]//Networked Knowledge-Networked Media:Integrating Knowledge Management, New Media Technologies and Semantic Systems, Berli, Heidelberg: Springer Berlin Heidelberg, 2009: 7-24.
[17]	FERNANDES D, BERNARDINO J. Graph Databases Comparison: AllegroGraph, ArangoDB, InfiniteGraph, Neo4J, and OrientDB[C]// Proceedings of the 7th International Conference on Data Science, Technology and Applications, 2018: 373-380.
[18]	ZOU L, MO J, CHEN L. gStore: answering SPARQL queries via subgraph matching[J]. Proceedings of the VLDB Endowment, 2011, 4(8): 482-493.
[19]	BUNCH C, CHOHAN N, KRINTZ C. Neptune: a domain specific language for deploying hpc software on cloud platforms[C]// Proceedings of the 2nd international workshop on Scientific cloud computing, 2011: 59-68.
[20]	KHURANA U, DESHPANDE A. Efficient snapshot retrieval over historical graph data[C]// 2013 IEEE 29th International Conference on Data Engineering (ICDE), IEEE, 2013: 997-1008.
[21]	DEBROUVIER A, PARODI E, PERAZZO M. A model and query language for temporal graph databases[J]. The VLDB Journal, 2021, 30(5): 825-858.
[22]	PAPAKONSTANTINOU V, FLOURIS G, FUNDULAKI I. Versioning for Linked Data: Archiving Systems and Benchmarks[C]// International Semantic Web Conference, 2016: 5.
[23]	XIANGYU L, YINGXIAO L, XIAOLIN G. An Efficient Snapshot Strategy for Dynamic Graph Storage Systems to Support Historical Queries[J]. IEEE Access, 2020, 8(1): 90838-90846.
[24]	FERNANDEZ G, JAVIER D. BEAR: Benchmarking the Efficiency of RDF Archiving[C]// Information Business and Operations, 2015: 2.
[25]	MEIMARIS M, PAPASTEFANATOS G. The EvoGen Benchmark Suite for Evolving RDF Data[C]// ESWC, 2016: 20-35.
[26]	ZENG C, HU C, WANG H. SciDG: Benchmarking Scientific Dynamic Graph Queries[C]// Proceedings of the 35th International Conference on Scientific and Statistical Database Management, 2023: 1-12.
[27]	FU D, HE J. DPPIN: A biological repository of dynamic protein-protein interaction network data[C]// 2022 IEEE International Conference on Big Data (Big Data), IEEE, 2022: 5269-5277.
[28]	ZHUANG H, SUN Y, TANG J. Influence maximization in dynamic social networks[C]// 2013 IEEE 13th international conference on data mining, IEEE, 2013: 1313-1318.
[29]	石川, 王睿嘉, 王啸. 异质信息网络分析与应用综述[J]. 软件学报, 2022, 33(2): 598-621.
[30]	孟祥保, 钱鹏. 国际图书情报学研究群体结构———以核心作者互引分析为视角[J]. 情报科学, 2015, 33(5): 124-128.
[31]	朱庆华, 李亮. 社会网络分析法及其在情报学中的应用[J]. 情报理论与实践, 2008(2): 179-83, 174
[32]	陈云伟. 社会网络分析方法在情报分析中的应用研究[J]. 情报学报, 2019, 38(1): 21-28.
[33]	朱彦君. 近十年图书情报学科学结构及演进研究[D]. 曲阜: 曲阜师范大学, 2018.
[34]	SANKAR A, WU Y, GOU L. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks[C]// Proceedings of the 13th international conference on web search and data mining, 2020: 519-527.
[35]	LE-KUI Z, YANG Y, XIANG R, FEI W, YUETING Z. Dynamic Network Embedding by Modeling Triadic Closure Process[C]. AAAI Conference on Artificial Intelligence, 2018: 571-578.
[36]	LUWEI Y, ZHIBO X, WEN J, YI W, YI H, HAO W. Dynamic Heterogeneous Graph Embedding Using Hierarchical Attentions[C]. European Conference on Information Retrieval, 2020: 425-432.
[37]	刘真, 吴向阳, 郑秋华. 动态网络可视化与可视分析综述[J]. 计算机辅助设计与图形学学报, 2016, 28(5): 693-701.
[38]	MICHAEL K. COLEMAN D. STOTT P. Aesthetics-based graph layout for human consumption[J]. Software-Practice and Experience, 1996, 26(12): 1415-1438.
[39]	FEDERICO P, AIGNER W, MIKSCH S. A visual analytics approach to dynamic social networks[C]// Proceedings of the 11th International Conference on Knowledge Management and Knowledge Technologies, 2011: 1-8.
[40]	VEHLOW C, BECK F, WEISKOPF D. The State of the Art in Visualizing Group Structures in Graphs[C]// Eurographics Conference on Visualization(EuroVis), STARs, 2015: 21-40.
[41]	BECK F, BURCH M, DIEHL S. Towards an aesthetic dimensions framework for dynamic graph visualisations[C]// 2009 13th international conference information visualisation, IEEE, 2009: 592-597.
[42]	BECK F, BURCH M, DIEHL S. Matching application requirements with dynamic graph visualization profiles[C]// 2013 17th international conference on information visualisation, IEEE, 2013: 11-18.