TY - JOUR
T1 - Subgraph Matching over Graph Federation
AU - Yuan, Ye
AU - Ma, Delong
AU - Wen, Zhenyu
AU - Zhang, Zhiwei
AU - Wang, Guoren
N1 - Publisher Copyright:
© 2021, VLDB Endowment. All rights reserved.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85126385152&partnerID=8YFLogxK
U2 - 10.14778/3494124.3494129
DO - 10.14778/3494124.3494129
M3 - Conference article
AN - SCOPUS:85126385152
SN - 2150-8097
VL - 15
SP - 437
EP - 450
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 3
T2 - 48th International Conference on Very Large Data Bases, VLDB 2022
Y2 - 5 September 2022 through 9 September 2022
ER -