Distributed subgraph matching on timely dataflow

Lai, L; Qing, Z; Yang, Z; Jin, X; Lai, Z; Wang, R; Hao, K; Lin, X; Qin, L; Zhang, W; Zhang, Y; Qian, Z; Zhou, J

Distributed subgraph matching on timely dataflow

Lai, L Qing, Z Yang, Z Jin, X Lai, Z Wang, R Hao, K Lin, X Qin, L

Zhang, W Zhang, Y

Qian, Z Zhou, J

Permalink

Publisher:: ASSOC COMPUTING MACHINERY
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2019, 12, (10), pp. 1099-1112
Issue Date:: 2019-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (1.19 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lai, L
dc.contributor.author	Qing, Z
dc.contributor.author	Yang, Z
dc.contributor.author	Jin, X
dc.contributor.author	Lai, Z
dc.contributor.author	Wang, R
dc.contributor.author	Hao, K
dc.contributor.author	Lin, X
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qian, Z
dc.contributor.author	Zhou, J
dc.date.accessioned	2022-01-31T04:47:39Z
dc.date.available	2022-01-31T04:47:39Z
dc.date.issued	2019-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2019, 12, (10), pp. 1099-1112
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/153949
dc.description.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 un-labelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.
dc.language	English
dc.publisher	ASSOC COMPUTING MACHINERY
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3339490.3339494
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	This work is licensed under the Creative Commons Attribution- NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 12, No. 10 ISSN 2150-8097. DOI: https://doi.org/10.14778/3339490.3339494
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Distributed subgraph matching on timely dataflow
dc.type	Journal Article
utslib.citation.volume	12
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2022-01-31T04:47:38Z
pubs.issue	10
pubs.publication-status	Published
pubs.volume	12
utslib.citation.issue	10

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 un-labelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/153949