Updates-aware 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 either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated G_P and G_D or incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we first analyze and detect the elimination relationships between the updates. Then, we construct an Elimination Hierarchy Tree (EH-Tree) to index these elimination relationships. In order to speed up the GPNM process, we propose a graph partition method and then propose a new updates-aware GPNM method, called UA-GPNM, considering the single-graph elimination relationships among the updates in a single graph of G_P or G_D, and also the cross-graph elimination relationships between the updates in G_P and the updates in G_D. UA-GPNM first delivers the GPNM result of an initial query, and then delivers the GPNM result of a subsequent query, based on the initial GPNM result and the multiple updates that occur between two queries. The experimental results on five real-world social graphs demonstrate that our proposed UA-GPNM is much more efficient than the state-of-the-art GPNM methods.