大规模图数据匹配技术综述

于静; 刘燕兵; 张宇; 刘梦雅; 谭建龙; 郭莉

doi:10.7544/issn1000-1239.2015.20140188

大规模图数据匹配技术综述

于静^1,3,
刘燕兵^1,3,
张宇^1,2,3,
刘梦雅^1,2,3,
谭建龙^1,3,
郭莉^1,3

¹(中国科学院信息工程研究所北京 100093)
²(中国科学院大学北京 100049)
³(信息内容安全技术国家工程实验室(中国科学院信息工程研究所) 北京 100093) (yujing02@iie.ac.cn)

基金项目: 国家自然科学基金项目(61202477)；中国科学院战略性科技先导专项基金项目(XDA06031000)；国家“八六三”高技术研究发展计划基金项目(2012AA012502)

详细信息

中图分类号: TP301
计量
- 文章访问数: 3528
- HTML全文浏览量: 13
- PDF下载量: 2882
出版历程
- 发布日期: 2015-01-31

Survey on Large-Scale Graph Pattern Matching

Yu Jing^1,3,
Liu Yanbing^1,3,
Zhang Yu^1,2,3,
Liu Mengya^1,2,3,
Tan Jianlong^1,3,
Guo Li^1,3

¹(Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093)
²(University of Chinese Academy of Sciences, Beijing 100049)
³(National Engineering Laboratory for Information Security Technologies (Institute of Information Engineering, Chinese Academy of Sciences), Beijing 100093)

摘要

摘要: 在大数据时代海量的多源异构数据间存在着紧密的关联性，图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述，根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时，将重点介绍精确图匹配，包括无索引的匹配和基于索引的匹配，以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结，并对该技术的未来发展趋势进行了展望.
- 图数据管理 /
- 图模式匹配 /
- 精确匹配 /
- 子图同构 /
- 索引技术 /
- 图搜索
Abstract: In the big data age, there exists close affinities among the great amount of multi-modal data. As a popular data model for representing the relations of different data, graph has been widely used in various fields such as analysis of social network, social security, and biological information. Fast and accurate search over the large-scale graph serves as a fundamental problem in graph analysis. In this paper, we survey the up-to-date development in graph pattern matching techniques for graph search from the application perspective. Graph pattern matching techniques are roughly classified into several categories according to the properties of graphs and the requirement of applications. Meanwhile, we focus on introducing and analyzing the exact pattern matching, including non-index matching, index-based matching and their key techniques, representative algorithms, and performance evaluation. We summarize the state-of-the-art applications, challenging issues, and research trends for graph pattern matching.
- graph management /
- graph pattern matching /
- exact matching /
- subgraph isomorphism /
- index techniques /
- graph search