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 G(P). 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, e.g., social graph searches on Facebook. To deliver a GPNM result in such applications, the existing GPNM methods have to perform an incremental GPNM procedure for each of the updates in the data graph, which is computationally expensive. To address this problem, in this paper, we first analyze the elimination relationships between multiple updates in G(D) 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, considering the elimination relationships between multiple updates in G(D). 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 G(D) 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.