ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (2): 391-409.doi: 10.7544/issn1000-1239.2015.20140188

所属专题: 2015大数据管理

• 综述 • 上一篇    下一篇

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

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

  1. 1(中国科学院信息工程研究所 北京 100093); 2(中国科学院大学 北京 100049); 3(信息内容安全技术国家工程实验室(中国科学院信息工程研究所) 北京 100093) (yujing02@iie.ac.cn)
  • 出版日期: 2015-02-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61202477);中国科学院战略性科技先导专项基金项目(XDA06031000);国家“八六三”高技术研究发展计划基金项目(2012AA012502)

Survey on Large-Scale Graph Pattern Matching

Yu Jing1,3, Liu Yanbing1,2,Zhang Yu1,2,3, Liu Mengya1,2,3,Tan Jianlong1,3,Guo Li1,3   

  1. 1(Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093); 2(University of Chinese Academy of Sciences, Beijing 100049) ; 3(National Engineering Laboratory for Information Security Technologies (Institute of Information Engineering, Chinese Academy of Sciences), Beijing 100093)
  • Online: 2015-02-01

摘要: 在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望.

关键词: 图数据管理, 图模式匹配, 精确匹配, 子图同构, 索引技术, 图搜索

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.

Key words: graph management, graph pattern matching, exact matching, subgraph isomorphism, index techniques, graph search

中图分类号: