ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (2): 391-409.doi: 10.7544/issn1000-1239.2015.20140188

Special Issue: 2015大数据管理

Previous Articles     Next Articles

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

CLC Number: