| 本文已被：浏览 7164次 下载 11522次 |
码上扫一扫！ |
|
|
| 动态图模式匹配技术综述 |
|
许嘉1,2,3, 张千桢1, 赵翔4, 吕品1,2,3, 李陶深1,2
|
|
1.广西大学 计算机与电子信息学院, 广西 南宁 530004;2.广西高校并行分布式计算技术重点实验室(广西大学), 广西 南宁 530004;3.广西高校多媒体通信与信息处理重点实验室(广西大学), 广西 南宁 530004;4.国防科技大学 系统工程学院, 湖南 长沙 410073
|
|
| 摘要: |
| 随着大数据时代的到来，多源异构数据的快速增长已经成为开放性问题，数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中，例如网络安全分析和社交网络舆情分析，描述实体对象之间关系的图数据的结构和内容往往不是固定不变的，图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此，如何在动态更新的图数据中进行高效的查询、匹配，是目前研究的热点问题.从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展.最后，对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望. |
| 关键词: 动态图 图模式匹配 子图同构 匹配算法 图搜索 |
| DOI：10.13328/j.cnki.jos.005444 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金（61402494，61402498，61402513）；广西自然科学基金青年基金（2015GXNSFBA139243，2016GXNSFBA380182）；广西大学科研基金（XGZ141182，XGZ150322）；广西高等教育本科教学改革工程重点项目（2017JGZ103） |
|
| Survey on Dynamic Graph Pattern Matching Technologies |
|
XU Jia1,2,3, ZHANG Qian-Zhen1, ZHAO Xiang4, LÜ Pin1,2,3, LI Tao-Shen1,2
|
|
1.School of Computer, Electronics and Information, Guangxi University, Nanning 530004, China;2.Guangxi Colleges and University Key Laboratory of Parallel and Distributed Computing Technology(Guangxi University), Nanning 530004, China;3.Guangxi Colleges and University Key Laboratory of Multimedia Communications and Information Processing(Guangxi University), Nanning 530004, China;4.College of System and Engineering, National University of Defense Technology, Changsha 410073, China
|
| Abstract: |
| With the advent of big data era, the rapid growth of multi-source heterogeneous data has become an open problem. The inherent relationships between these data are usually modeled by the graph model. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and content of the graph data describing relationships between entity objects are usually not fixed. To be specific, the structure of the graph data, and the attributes of the nodes and edges in it will vary over time. Therefore, efficient query and match over dynamically updated graph data currently draws extensive research, where many outstanding research works are proposed. In this paper, the research progress of dynamic graph data matching technologies is reviewed from the aspects of key technologies, representative algorithms and performance evaluation. The state-of-the-art applications, the challenging problems and the research trend of dynamic graph matching technologies are summarized. |
| Key words: dynamic graph graph pattern matching subgraph isomorphism matching algorithm graph search |
