Partition-aware graph pattern based node matching with updates

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

Research output: Contribution to journalArticlepeer-review

Abstract

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. The existing GPNM methods either need to perform a new GPNM procedure from scratch 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. The experimental results on five social graphs demonstrate that our proposed P-GPNM is much more efficient than the state-of-the-art GPNM methods.

Original languageEnglish
JournalIEEE Transactions on Knowledge and Data Engineering
DOIs
Publication statusE-pub ahead of print - 10 Aug 2021

Bibliographical note

Publisher Copyright:
IEEE

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Australia
  • Data models
  • elimination relationship
  • Fans
  • Graph pattern matching
  • Indexes
  • Pattern matching
  • Social networking (online)
  • Sun
  • updates of graph

Fingerprint

Dive into the research topics of 'Partition-aware graph pattern based node matching with updates'. Together they form a unique fingerprint.

Cite this