Distributed Subgraph Matching on Timely Dataflow
Longbin Lai, Zhu Qing, Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, Xuemin Lin, Lu Qin, Wenjie Zhang, Ying Zhang, Zhengping Qian, Jingren Zhou
RAIDS Lab Authors
Details
Research Area
Tags
Resources
Abstract
Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view of distributed subgraph matching mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art algorithms. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy-level comparison. Our implementation covers all representative algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.
Author Affiliations
BibTeX
@article{lai2019distributed,
title = {Distributed subgraph matching on timely dataflow},
author = {Lai, Longbin and Qing, Zhu and Yang, Zhengyi and Jin, Xin and Lai, Zhengmin and Wang, Ran and Hao, Kongzhang and Lin, Xuemin and Qin, Lu and Zhang, Wenjie and Zhang, Ying and Qian, Zhengping and Zhou, Jingren},
volume = {12},
issn = {2150-8097},
url = {http://dx.doi.org/10.14778/3339490.3339494},
doi = {10.14778/3339490.3339494},
number = {10},
journal = {Proceedings of the VLDB Endowment},
publisher = {Association for Computing Machinery (ACM)},
year = {2019},
month = June,
pages = {1099-1112}
}