大规模动态图版本化管理：需求、技术与挑战

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

数据与计算发展前沿 ›› 2024, Vol. 6 ›› Issue (4): 77-86.

CSTR: 32002.14.jfdc.CN10-1649/TP.2024.04.006

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

• 专刊：面向国家科学数据中心的基础软件栈及系统 • 上一篇下一篇

大规模动态图版本化管理：需求、技术与挑战

曾成林^1,²(),王华进^1,²,朱小杰^1,²,沈志宏^1,^2,^*()

1.中国科学院计算机网络信息中心，北京 100083
2.中国科学院大学，北京 100049

收稿日期:2024-02-05 出版日期:2024-08-20 发布日期:2024-08-20
通讯作者: *沈志宏（E-mail: bluejoe@cnic.cn）
作者简介:曾成林，中国科学院计算机网络信息中心，中国科学院大学，博士研究生，CCF会员，主要研究方向为图数据库、数据管理。
本文承担工作为文献调研，实验数据收集，实验设计，论文写作。
ZENG Chenglin, member of China Computer Federation (CCF), a Master’s student at the Computer Network Information Center, Chinese Academy of Sciences, and the University of Chinese Academy of Sciences. His main research interests are graph databases and data management.
In this paper, he undertakes the following tasks: literature review, experimental data collection, experimental design, and paper writing.
E-mail: zengchenglin@cnic.cn|沈志宏，中国科学院计算机网络信息中心，大数据技术与应用发展部主任，同时担任大数据分析与计算技术国家地方联合工程实验室总工程师。正研级高级工程师，博士生导师，CCF会员。主要研究方向为科学大数据、图数据管理技术。主持开发了大数据流水线PiFlow、异构数据融合管理系统PandaDB等开源软件。
本文承担工作为论文整体框架设计，研究指导。
SHEN Zhihong, Ph.D., professor, doctoral supervisor. Director of the Department of Big Data Technology and Application Development at the Computer Network Information Center, Chinese Academy of Sciences. Simultaneously serving as the Chief Engineer of the National-Local Joint Engineering Laboratory for Big Data Analysis and Computing Technology. He holds the position of Senior Engineer at the research level, doctoral supervisor, member of China Computer Federation (CCF), and his main research focuses on scientific big data and graph data management technology. He has led the development of open-source software such as the big data pipeline PiFlow and the heterogeneous data fusion management system PandaDB.
In this paper, he undertakes the following tasks: the overall framework design and research guidance of the thesis.
E-mail: bluejoe@cnic.cn
基金资助:
国家重点研发计划项目“面向国家科学数据中心的基础软件栈及系统”(2021YFF0704200);中国科学院“十四五”网信专项工程建设项目“科学大数据工程（三期）”(CAS-WX2022GC-02)

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

ZENG Chenglin^1,²(),WANG Huajin^1,²,ZHU Xiaojie^1,²,SHEN Zhihong^1,^2,^*()

1. Computer Network Information Center, The Chinese Academy of Sciences, Beijing 100083, China
2. University of Chinese Academy of Sciences, Beijing 100049, China

Received:2024-02-05 Online:2024-08-20 Published:2024-08-20

摘要/Abstract

摘要：

【目的】 在大数据时代，从生活生产到科研领域，产生了海量的动态图数据，对这些数据进行管理和分析可以有效地辅助人们进行工艺设计、智能决策和科学研究。【文献范围】本文使用动态图、演化图和版本图管理等关键字在知网和谷歌学术上进行搜索，整理收集了几十篇相关文献。【方法】 本文以数据模型、管理系统和挖掘分析方法三大类为依据对相关研究文献进行分类和归纳总结，分析了国内外研究现状。【结果】 其中对动态图数据三种主流存储策略的空间消耗情况在理论上进行了研究并得到了初步结论，其次从集合的角度对现有的动态图查询需求进行了更深层次的总结，最后从论文的分类数量发现当前对动态图的研究更侧重于挖掘分析方面。【局限】本文整理收集的相关文献包含的图模型以属性图为主，RDF相关的文献并未涉及。【结论】 本文在分析了大规模动态图版本化管理的相关需求与技术后，也提出了存在的一些挑战，包括动态图多版本管理带来的高空间膨胀率、指定版本的高效随机检索和版本之间的演变关系精准刻画等问题。

关键词: 动态图, 版本化管理, 图数据

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

曾成林, 王华进, 朱小杰, 沈志宏. 大规模动态图版本化管理：需求、技术与挑战[J]. 数据与计算发展前沿, 2024, 6(4): 77-86.

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.

图/表 2

参考文献 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.

大规模动态图版本化管理：需求、技术与挑战

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 42

相关文章 1

编辑推荐

Metrics

本文评价