Abstract
Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. However, the existing GPNM methods need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GP and updated GD, which consumes much time. Therefore, there is a pressing need for a novel method to efficiently deliver the node matching results. In this paper, we propose a novel INCremental GPNM method called INC-GPNM, where we first build up indices to incrementally maintain the shortest path length range between different label types in GD, and then identify the affected parts of GD in GPNM including nodes and edges w.r.t. the updates of GP and GD. Moreover, based on the index structure and our novel search strategies, INC-GPNM can efficiently deliver node matching results taking the updates of GP and GD as input, and can greatly save the query processing time with improved time complexity. The extensive experiments on five real-world social graphs demonstrate that our method greatly outperforms the state-of-the-art GPNM method in efficiency.
Original language | English |
---|---|
Title of host publication | 2018 IEEE 34th International Conference on Data Engineering (ICDE) |
Place of Publication | Piscataway, NJ |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 281-292 |
Number of pages | 12 |
ISBN (Electronic) | 9781538655207 |
DOIs | |
Publication status | Published - 24 Oct 2018 |
Event | IEEE 34th International Conference on Data Engineering (ICDE 2018) - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018 |
Conference
Conference | IEEE 34th International Conference on Data Engineering (ICDE 2018) |
---|---|
Country/Territory | France |
City | Paris |
Period | 16/04/18 → 19/04/18 |
Keywords
- Graph
- Graph Pattern Matching
- Incremental