{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:18:04Z","timestamp":1789435084031,"version":"build-2803163510"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key R$\\&$D Programs of China","award":["2021ZD40303"],"award-info":[{"award-number":["2021ZD40303"]}]},{"name":"Shenzhen Science and Technology Program and Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, National Natural Science Foundation of China Innovation Research Group Project","award":["62321003"],"award-info":[{"award-number":["62321003"]}]},{"name":"Shenzhen Science and Technology Program","award":["JCYJ20220530143602006 and ZDSYS 20211021111415025"],"award-info":[{"award-number":["JCYJ20220530143602006 and ZDSYS 20211021111415025"]}]},{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62102341, 62302421, 62172146, and U23A20317"],"award-info":[{"award-number":["62102341, 62302421, 62172146, and U23A20317"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2022A1515010166 and 2023A1515011280"],"award-info":[{"award-number":["2022A1515010166 and 2023A1515011280"]}]},{"name":"Guangdong Talent Program","award":["2021QN02X826"],"award-info":[{"award-number":["2021QN02X826"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>The enumeration of hop-constrained simple paths is a building block in many graph-based areas. Due to the enormous search spaces in large-scale graphs, a single machine can hardly satisfy the requirements of both efficiency and memory, which causes an urgent need for efficient distributed methods. In practice, it is inevitable to produce plenty of intermediate results when directly extending centralized methods to the distributed environment, thereby causing a memory crisis and weakening the query performance. The state-of-the-art distributed method HybridEnum designed a hybrid search paradigm to enumerate simple paths. However, it makes massive exploration for the redundant vertices not located in any simple path, thereby resulting in poor query performance. To alleviate this problem, we design a distributed approach DistriEnum to optimize query performance and scalability with well-bound memory consumption. Firstly, DistriEnum adopts a graph reduction strategy to rule out the redundant vertices without satisfying the constraint of hop number. Then, a core search paradigm is designed to simultaneously reduce the traversal of shared subpaths and the storage of intermediate results. Moreover, DistriEnum is equipped with a task division strategy to theoretically achieve workload balance. Finally, a vertex migration strategy is devised to reduce the communication cost during the enumeration. The comprehensive experimental results on 10 real-world graphs demonstrate that DistriEnum achieves up to 3 orders of magnitude speedup than HybridEnum in query performance and exhibits superior performances on scalability, communication cost, and memory consumption.<\/jats:p>","DOI":"10.1145\/3639277","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-25","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-6476","authenticated-orcid":false,"given":"Yuanyuan","family":"Zeng","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Sehnzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0764-0620","authenticated-orcid":false,"given":"Xu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2635-7716","authenticated-orcid":false,"given":"Kenli","family":"Li","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. ACM 349--360.","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2756553"},{"key":"e_1_2_1_3_1","volume-title":"An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs","author":"Bhattacharya Sayan","unstructured":"Sayan Bhattacharya and Janardhan Kulkarni. 2020. An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs. In SODA. SIAM, 2509--2521."},{"key":"e_1_2_1_4_1","volume-title":"Optimal Listing of Cycles and st-Paths in Undirected Graphs","author":"Birmel\u00e9 Etienne","year":"1884","unstructured":"Etienne Birmel\u00e9, Rui A. Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. 2013. Optimal Listing of Cycles and st-Paths in Undirected Graphs. In SODA. SIAM, 1884--1896."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3198394.3198410"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.12656"},{"key":"e_1_2_1_7_1","volume-title":"Jeffrey Xu Yu, and Jian Pei","author":"Chang Lijun","year":"2015","unstructured":"Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Jian Pei. 2015. Efficiently Computing Top-K Shortest Path Join. In EDBT. OpenProceedings.org, 133--144."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467873"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_40"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Sairam Gurajada and Martin Theobald. 2016. Distributed Set Reachability. In SIGMOD. ACM 1247--1261.","DOI":"10.1145\/2882903.2915226"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071382"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489499"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_16_1","first-page":"930","article-title":"Pathways Database System","volume":"19","author":"Krishnamurthy Larkshmi","year":"2003","unstructured":"Larkshmi Krishnamurthy, Joseph H. Nadeau, Gultekin \u00d6zsoyoglu, Z. Meral \u00d6 zsoyoglu, Greg Schaeffer, Murat Tasan, and Wanhong Xu. 2003. Pathways Database System: An Integrated System for Biological Pathways. Bioinform., Vol. 19, 8 (2003), 930--937.","journal-title":"An Integrated System for Biological Pathways. Bioinform."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236197"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556571"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2019. Scaling Distance Labeling on Small-World Networks. In SIGMOD. ACM 1060--1077.","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2020. Scaling Up Distance Labeling on Graphs with Core-Periphery Properties. In SIGMOD. ACM 1367--1381.","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Masaaki Nishino Norihito Yasuda Shin-ichi Minato and Masaaki Nagata. 2017. Compiling Graph Substructures into Sentential Decision Diagrams. In AAAI. 1213--1221.","DOI":"10.1609\/aaai.v31i1.10697"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00695-0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Michalis Potamias Francesco Bonchi Carlos Castillo and Aristides Gionis. 2009. Fast shortest path distance estimation in large networks. In CIKM. ACM 867--876.","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2016.04.015"},{"key":"e_1_2_1_27_1","volume-title":"Finding Streams in Knowledge Graphs to Support Fact Checking","author":"Shiralkar Prashant","unstructured":"Prashant Shiralkar, Alessandro Flammini, Filippo Menczer, and Giovanni Luca Ciampaglia. 2017. Finding Streams in Knowledge Graphs to Support Fact Checking. In ICDM. IEEE Computer Society, 859--864."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Shixuan Sun Yuhang Chen Bingsheng He and Bryan Hooi. 2021. PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration. In SIGMOD. ACM 1758--1770.","DOI":"10.1145\/3448016.3457290"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Lucien D. J. Valstar George H. L. Fletcher and Yuichi Yoshida. 2017. Landmark Indexing for Evaluation of Label-Constrained Reachability Queries. In SIGMOD. ACM 345--358.","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_30_1","volume-title":"Efficiently Answering Span-Reachability Queries in Large Temporal Graphs","author":"Wen Dong","unstructured":"Dong Wen, Yilun Huang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2020. Efficiently Answering Span-Reachability Queries in Large Temporal Graphs. In ICDE. IEEE, 1153--1164."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_32_1","volume-title":"AMBN (Proceedings of Machine Learning Research","volume":"140","author":"Yasuda Norihito","year":"2017","unstructured":"Norihito Yasuda, Teruji Sugaya, and Shin-ichi Minato. 2017. Fast Compilation of s-t Paths on a Graph for Counting and Enumeration. In AMBN (Proceedings of Machine Learning Research, Vol. 73). PMLR, 129--140."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3139111"},{"key":"e_1_2_1_34_1","volume-title":"Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs","author":"Zeng Yuanyuan","unstructured":"Yuanyuan Zeng, Wangdong Yang, Xu Zhou, Guoqin Xiao, Yunjun Gao, and Kenli Li. 2022b. Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs. In ICDE. IEEE."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589408"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639277","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:34Z","timestamp":1755789274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639277"],"URL":"https:\/\/doi.org\/10.1145\/3639277","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}