Incremental Graph Pattern based Node Matching

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph G_D based on a given pattern graph G_P. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both G_P and G_D 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 G_P and updated G_D, 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 G_D, and then identify the affected parts of G_D in GPNM including nodes and edges w.r.t. the updates of G_P and G_D. Moreover, based on the index structure and our novel search strategies, INC-GPNM can efficiently deliver node matching results taking the updates of G_P and G_D 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.