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

Survey on Large-Scale Graph Pattern Matching

作　　者：于静[1,2] 刘燕兵[1,2] 张宇[1,3,2] 刘梦雅[1,3,2] 谭建龙[1,2] 郭莉[1,2] 

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]信息内容安全技术国家工程实验室(中国科学院信息工程研究所),北京100093 [3]中国科学院大学,北京100049

出　　处：《计算机研究与发展》2015年第2期391-409,共19页Journal of Computer Research and Development

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

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]