Incremental Graph Pattern based Node Matching with Multiple Updates

Graph Pattern based Node Matching (GPNM) has been proposed to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has been increasingly adopted in many applications such as group finding and expert recommendation, in which data graphs are frequently updated over time. Moreover, many typical pattern graphs frequently and repeatedly appear in users' queries in a short period of time. The existing GPNM methods have to perform an incremental GPNM procedure for each update in GD. In this paper, we first analyze the elimination relationships between multiple updates in GD and the hierarchical structure between these elimination relationships. Then, we generate an Elimination Hierarchy Tree (EH-Tree) to index the elimination relationships and propose an EH-Tree based GPNM method, called EH-GPNM. EH-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 of GD that occur between those two queries. The experimental results on five real-world social graphs demonstrate that our proposed EH-GPNM is much more efficient than the state-of-the-art GPNM methods