.png){kind=icon}
.png){kind=icon}
Return
Partition-Aware Graph Pattern Based Node Matching With Updates
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2021.3103914.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. Although the elimination relations between updates and partitions of data graphs are considered in the state-of-the-art method, it still suffers from low efficiency as only the labels of nodes are considered in the partitions. 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 propose a new Partition-aware GPNM algorithm, called P-GPNM, where we propose two new partition methods, i.e., connection-based partition and density-based partition. In these two methods, P-GPNM considers the dense connections between partitions and the inner connections inside a single partition, respectively. The experimental results on five real-world social graphs demonstrate that our proposed P-GPNM is much more efficient than the state-of-the-art GPNM methods.
Keywords:
Graph pattern matching
updates of graph
elimination relationship
graph partition
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W