A survey of continuous subgraph matching for dynamic graphs
Open Access
- 19 October 2022
- journal article
- research article
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 65 (3) , 945-989
Abstract
With the rapid development of information technologies, multi-source heterogeneous data has become an open problem, and the data is usually modeled as graphs since the graph structure is able to encode complex relationships among entities. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and the content of graph data are constantly evolving. Therefore, the ability to continuously monitor and detect interesting patterns on massive and dynamic graphs in real-time is crucial for many applications. Recently, a large group of excellent research works has also emerged. Nevertheless, these studies focus on different updates of graphs and apply different subgraph matching algorithms; thus, it is desirable to review these works comprehensively and give a thorough overview. In this paper, we systematically investigate the existing continuous subgraph matching techniques from the aspects of key techniques, representative algorithms, and performance evaluation. Furthermore, the typical applications and challenges of continuous subgraph matching over dynamic graphs, as well as the future development trends, are summarized and prospected.Keywords
Funding Information
- National key research and development program (2018YFE0207600)
- National Natural Science Foundation of China (U19B2024)
- National Natural Science Foundation of China (61872446)
- The science and technology innovation Program of Hunan Province (2020RC4046)
This publication has 72 references indexed in Scilit:
- Efficient Multiview Maintenance under Insertion in Huge Social NetworksACM Transactions on the Web, 2014
- Skew strikes backACM SIGMOD Record, 2014
- Capturing topology in graph pattern matchingProceedings of the VLDB Endowment, 2011
- BR-Index: An Indexing Structure for Subgraph Matching in Very Large Dynamic Graphs2011
- On graph query optimization in large networksProceedings of the VLDB Endowment, 2010
- C-SPARQL: A CONTINUOUS QUERY LANGUAGE FOR RDF DATA STREAMSInternational Journal of Semantic Computing, 2010
- Taming verification hardnessProceedings of the VLDB Endowment, 2008
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactionsNucleic Acids Research, 2002
- A bridging model for parallel computationCommunications of the ACM, 1990