{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:50Z","timestamp":1773895310254,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3339490.3339494","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1099-1112","source":"Crossref","is-referenced-by-count":66,"title":["Distributed subgraph matching on timely dataflow"],"prefix":"10.14778","volume":"12","author":[{"given":"Longbin","family":"Lai","sequence":"first","affiliation":[{"name":"The University of New South Wales, Sydney, Australia and Zhejiang Lab, China"}]},{"given":"Zhu","family":"Qing","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Zhengyi","family":"Yang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia and East China Normal University, China"}]},{"given":"Xin","family":"Jin","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Zhengmin","family":"Lai","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Ran","family":"Wang","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Kongzhang","family":"Hao","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia and East China Normal University, China and Zhejiang Lab, China"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}]},{"given":"Zhengping","family":"Qian","sequence":"additional","affiliation":[{"name":"Alibaba Group, China"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, China"}]}],"member":"320","published-online":{"date-parts":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The challenge9 datasets. http:\/\/www.dis.uniroma1.it\/challenge9.  The challenge9 datasets. http:\/\/www.dis.uniroma1.it\/challenge9."},{"key":"e_1_2_1_2_1","unstructured":"The clubweb12 dataset. https:\/\/lemurproject.org\/clueweb12.  The clubweb12 dataset. https:\/\/lemurproject.org\/clueweb12."},{"key":"e_1_2_1_3_1","unstructured":"Compressed sparse row. https:\/\/en.wikipedia.org\/wiki\/Sparse_matrix.  Compressed sparse row. https:\/\/en.wikipedia.org\/wiki\/Sparse_matrix."},{"key":"e_1_2_1_4_1","unstructured":"Distributed subgraph matching on timely dataflow -the full paper. https:\/\/goo.gl\/zkTkL4.  Distributed subgraph matching on timely dataflow -the full paper. https:\/\/goo.gl\/zkTkL4."},{"key":"e_1_2_1_5_1","unstructured":"Giraph. http:\/\/giraph.apache.org\/.  Giraph. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_6_1","unstructured":"The implementation of bigjoin. https:\/\/github.com\/frankmcsherry\/dataflow-join\/.  The implementation of bigjoin. https:\/\/github.com\/frankmcsherry\/dataflow-join\/."},{"key":"e_1_2_1_7_1","unstructured":"Ldbc benchmarks. http:\/\/ldbcouncil.org\/benchmarks.  Ldbc benchmarks. http:\/\/ldbcouncil.org\/benchmarks."},{"key":"e_1_2_1_8_1","unstructured":"The ldbc social network benchmark. https:\/\/ldbc.github.io\/ldbc_snb_docs\/ldbc-snb-specification.pdf.  The ldbc social network benchmark. https:\/\/ldbc.github.io\/ldbc_snb_docs\/ldbc-snb-specification.pdf."},{"key":"e_1_2_1_9_1","unstructured":"The open-sourced timely dataflow system. https:\/\/github.com\/frankmcsherry\/timely-dataflow.  The open-sourced timely dataflow system. https:\/\/github.com\/frankmcsherry\/timely-dataflow."},{"key":"e_1_2_1_10_1","unstructured":"The snap datasets. http:\/\/snap.stanford.edu\/data\/index.html.  The snap datasets. http:\/\/snap.stanford.edu\/data\/index.html."},{"key":"e_1_2_1_11_1","unstructured":"The webgraph datasets. http:\/\/law.di.unimi.it\/datasets.php.  The webgraph datasets. http:\/\/law.di.unimi.it\/datasets.php."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544814"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3199517.3199520"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_16_1","volume-title":"Apache flink: Stream and batch processing in a single engine. 38, 01","author":"Carbone P.","year":"2015","unstructured":"P. Carbone , A. Katsifodimos , . Kth, S. Sweden , S. Ewen , V. Markl , S. Haridi , and K. Tzoumas . Apache flink: Stream and batch processing in a single engine. 38, 01 2015 . P. Carbone, A. Katsifodimos, . Kth, S. Sweden, S. Ewen, V. Markl, S. Haridi, and K. Tzoumas. Apache flink: Stream and batch processing in a single engine. 38, 01 2015."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_18_1","volume-title":"EDBT","author":"Choudhury S.","year":"2015","unstructured":"S. Choudhury , L. B. Holder , G. Chin , K. Agarwal , and J. Feo . A selectivity based approach to continuous pattern detection in streaming graphs . In EDBT , 2015 . S. Choudhury, L. B. Holder, G. Chin, K. Agarwal, and J. Feo. A selectivity based approach to continuous pattern detection in streaming graphs. In EDBT, 2015."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_20_1","volume-title":"The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3)","author":"Chung F. R. K.","year":"2003","unstructured":"F. R. K. Chung , L. Lu , and V. H. Vu . The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3) , 2003 . F. R. K. Chung, L. Lu, and V. H. Vu. The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3), 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/122058.122071"},{"key":"e_1_2_1_22_1","volume-title":"Publ. Math. Inst. Hungary. Acad. Sci.","author":"Erdos P.","year":"1960","unstructured":"P. Erdos and A. Renyi . On the evolution of random graphs . In Publ. Math. Inst. Hungary. Acad. Sci. , 1960 . P. Erdos and A. Renyi. On the evolution of random graphs. In Publ. Math. Inst. Hungary. Acad. Sci., 1960."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758222.1758229"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735497"},{"key":"e_1_2_1_27_1","volume-title":"The Art of Multiprocessor Programming","author":"Herlihy M.","year":"2008","unstructured":"M. Herlihy and N. Shavit . The Art of Multiprocessor Programming . 2008 . M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. 2008."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735518"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115813"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0459-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_37_1","volume-title":"HOTOS'15","author":"McSherry F.","year":"2015","unstructured":"F. McSherry , M. Isard , and D. G. Murray . Scalability! but at what cost ? HOTOS'15 , 2015 . F. McSherry, M. Isard, and D. G. Murray. Scalability! but at what cost? HOTOS'15, 2015."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/523986.857995"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_49_1","volume-title":"ICDT","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . Triejoin : A simple, worst-case optimal join algorithm . In ICDT , 2014 . T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT, 2014."},{"key":"e_1_2_1_50_1","volume-title":"Vertex priority based butterfly counting for large-scale bipartite networks. arXiv preprint arXiv:1812.00283","author":"Wang K.","year":"2018","unstructured":"K. Wang , X. Lin , L. Qin , W. Zhang , and Y. Zhang . Vertex priority based butterfly counting for large-scale bipartite networks. arXiv preprint arXiv:1812.00283 , 2018 . K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang. Vertex priority based butterfly counting for large-scale bipartite networks. arXiv preprint arXiv:1812.00283, 2018."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_1_52_1","first-page":"10","volume-title":"HotCloud'10","author":"Zaharia M.","unstructured":"M. Zaharia , M. Chowdhury , M. J. Franklin , S. Shenker , and I. Stoica . Spark: Cluster computing with working sets . In HotCloud'10 , pages 10 -- 10 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster computing with working sets. In HotCloud'10, pages 10--10."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:25:55Z","timestamp":1672223155000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":52,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339494"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339494","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}