Incremental graph pattern based node matching with multiple updates

Guohao Sun, Guanfeng Liu, Yan Wang, Mehmet Orgun, Quan Z. Sheng, Xiaofang Zhou

Research output: Contribution to journalArticlepeer-review

Abstract

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, 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 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, considering the elimination relationships between multiple updates in G. 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.

Original languageEnglish
Pages (from-to)1585-1600
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume33
Issue number4
Early online date19 Sep 2019
DOIs
Publication statusPublished - Apr 2021

Keywords

  • Graph pattern matching
  • updates of graph
  • elimination relationship

Cite this