Subgraph Matching over Graph Federation

Ye Yuan, Delong Ma, Zhenyu Wen, Zhiwei Zhang, Guoren Wang

Research output: Contribution to journalConference articlepeer-review

9 Citations (Scopus)

Abstract

Many real-life applications require processing graph data across heterogeneous sources. In this paper, we define the graph federation that indicates that the graph data sources are temporarily federated and offer their data for users. Next, we propose a new framework FedGraph to efficiently and effectively perform subgraph matching, which is a crucial application in graph federation. FedGraph consists of three phases, including query decomposition, distributed matching, and distributed joining. We also develop new efficient approximation algorithms and apply them in each phase to attack the NP-hard problem. The evaluations are conducted in a real test bed using both real-life and synthetic graph datasets. FedGraph outperforms the state-of-the-art methods, reducing the execution time and communication cost by 37.3 × and 61.8 ×, respectively.

Original languageEnglish
Pages (from-to)437-450
Number of pages14
JournalProceedings of the VLDB Endowment
Volume15
Issue number3
DOIs
Publication statusPublished - 2021
Event48th International Conference on Very Large Data Bases, VLDB 2022 - Sydney, Australia
Duration: 5 Sept 20229 Sept 2022

Fingerprint

Dive into the research topics of 'Subgraph Matching over Graph Federation'. Together they form a unique fingerprint.

Cite this