{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:58Z","timestamp":1773481978338,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>\n            Hop-constrained\n            <jats:italic>s-t<\/jats:italic>\n            simple path (HC-s-t path) enumeration is a fundamental problem in graph analysis and has received considerable attention recently. Straightforward distributed solutions are inefficient and suffer from poor scalabiltiy when addressing this problem in billion-scale graphs due to the disability of pruning fruitless exploration or huge memory consumption. Motivated by this, in this paper, we aim to devise an efficient and scalable distributed algorithm to enumerate the HC-s-t paths in billion-scale graphs. We first propose a new hybrid search paradigm tailored for HC-s-t path enumeration. Based on the new search paradigm, we devise a distributed enumeration algorithm following the divide-and-conquer strategy. The algorithm can not only prune fruitless exploration, but also well bound the memory consumption with high parallelism. We also devise an effective workload balance mechanism that is automatically triggered by the idle machines to handle skewed workloads. Moreover, we explore the bidirectional search strategy to further improve enumeration efficiency. The experiment results demonstrate the efficiency of our proposed algorithm.\n          <\/jats:p>","DOI":"10.14778\/3489496.3489499","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"169-182","source":"Crossref","is-referenced-by-count":26,"title":["Distributed hop-constrained s-t simple path enumeration at billion scale"],"prefix":"10.14778","volume":"15","author":[{"given":"Kongzhang","family":"Hao","sequence":"first","affiliation":[{"name":"University of New South Wales"}]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[{"name":"Nanjing University of Science and Technology"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3199517.3199520"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_4_1","volume-title":"GA","author":"Bader David","year":"2006","unstructured":"David A Bader and KameshMadduri. 2006 . Gtgraph:A synthetic graph generator suite. Atlanta , GA , February 38 (2006). David ABader and KameshMadduri. 2006. Gtgraph:A synthetic graph generator suite. Atlanta, GA, February 38 (2006)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2080.357392"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513591.2527070"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380119"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078606"},{"key":"e_1_2_1_12_1","unstructured":"LAW Dataset. EU-2015. http:\/\/law.di.unimi.it\/webdata\/eu-2015\/.  LAW Dataset. EU-2015. http:\/\/law.di.unimi.it\/webdata\/eu-2015\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960416"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_15_1","volume-title":"Dorgival Guedes, Wagner Meira, and Srinivasan Parthasarathy.","author":"Dias Vinicius","year":"2019","unstructured":"Vinicius Dias , Carlos HC Teixeira , Dorgival Guedes, Wagner Meira, and Srinivasan Parthasarathy. 2019 . Fractal Open Source Implementation . https:\/\/github.com\/dccspeed\/fractal Vinicius Dias, Carlos HC Teixeira, Dorgival Guedes, Wagner Meira, and Srinivasan Parthasarathy. 2019. Fractal Open Source Implementation. https:\/\/github.com\/dccspeed\/fractal"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07983-7_3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_40"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357840"},{"key":"e_1_2_1_20_1","unstructured":"Kongzhang Hao Long Yuan and Wenjie Zhang. 2021. Technical Report. https:\/\/www.dropbox.com\/s\/3ea2h9azy5llpjp\/technical%20report.pdf?dl=0  Kongzhang Hao Long Yuan and Wenjie Zhang. 2021. Technical Report. https:\/\/www.dropbox.com\/s\/3ea2h9azy5llpjp\/technical%20report.pdf?dl=0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.03.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3291168.3291226"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277395"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg113"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5205-8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1105"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324306"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171812"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300076"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00019"},{"key":"e_1_2_1_42_1","volume-title":"Answering reachability and K-reach queries on large graphs with label constraints. The VLDB Journal","author":"Peng You","year":"2021","unstructured":"You Peng , Xuemin Lin , Ying Zhang , Wenjie Zhang , and Lu Qin . 2021. Answering reachability and K-reach queries on large graphs with label constraints. The VLDB Journal ( 2021 ), 1--27. You Peng, Xuemin Lin, Ying Zhang, Wenjie Zhang, and Lu Qin. 2021. Answering reachability and K-reach queries on large graphs with label constraints. The VLDB Journal (2021), 1--27."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00110"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342272"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19315-1_28"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_51_1","volume-title":"Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. The VLDB Journal","author":"Wang Kai","year":"2021","unstructured":"Kai Wang , Xuemin Lin , Lu Qin , Wenjie Zhang , and Ying Zhang . 2021. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. The VLDB Journal ( 2021 ), 1--24. Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2021. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. The VLDB Journal (2021), 1--24."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3040172"},{"key":"e_1_2_1_53_1","volume-title":"Discovering Significant Communities on Bipartite Graphs: An Index-based Approach","author":"Wang Kai","year":"2021","unstructured":"Kai Wang , Wenjie Zhang , Ying Zhang , Lu Qin , and Yuting Zhang . 2021. Discovering Significant Communities on Bipartite Graphs: An Index-based Approach . IEEE Transactions on Knowledge and Data Engineering ( 2021 ). Kai Wang, Wenjie Zhang, Ying Zhang, Lu Qin, and Yuting Zhang. 2021. Discovering Significant Communities on Bipartite Graphs: An Index-based Approach. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00021"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157802"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/WICOM.2007.1352"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824041"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026901"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:07Z","timestamp":1672225867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489499"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489499","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}