Incremental Graph Pattern based Node Matching

Guohao Sun, Guanfeng Liu, Yan Wang, Mehmet Orgun, Xiaofang Zhou

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

5 Citations (Scopus)

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. However, the existing GPNM methods need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GP and updated GD, which consumes much time. Therefore, there is a pressing need for a novel method to efficiently deliver the node matching results. In this paper, we propose a novel INCremental GPNM method called INC-GPNM, where we first build up indices to incrementally maintain the shortest path length range between different label types in GD, and then identify the affected parts of GD in GPNM including nodes and edges w.r.t. the updates of GP and GD. Moreover, based on the index structure and our novel search strategies, INC-GPNM can efficiently deliver node matching results taking the updates of GP and GD as input, and can greatly save the query processing time with improved time complexity. The extensive experiments on five real-world social graphs demonstrate that our method greatly outperforms the state-of-the-art GPNM method in efficiency.
Original languageEnglish
Title of host publication2018 IEEE 34th International Conference on Data Engineering (ICDE)
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages281-292
Number of pages12
ISBN (Electronic)9781538655207
DOIs
Publication statusPublished - 24 Oct 2018
EventIEEE 34th International Conference on Data Engineering (ICDE 2018) - Paris, France
Duration: 16 Apr 201819 Apr 2018

Conference

ConferenceIEEE 34th International Conference on Data Engineering (ICDE 2018)
CountryFrance
CityParis
Period16/04/1819/04/18

Keywords

  • Graph
  • Graph Pattern Matching
  • Incremental

Fingerprint

Dive into the research topics of 'Incremental Graph Pattern based Node Matching'. Together they form a unique fingerprint.

Cite this