{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T04:15:07Z","timestamp":1789100107706,"version":"build-2803163510"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T00:00:00Z","timestamp":1741564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740850, CCF-1839317, CCF-2402572, DMS-2023495"],"award-info":[{"award-number":["CCF-1740850, CCF-1839317, CCF-2402572, DMS-2023495"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,3,10]]},"DOI":"10.1145\/3701551.3703512","type":"proceedings-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T12:33:36Z","timestamp":1740573216000},"page":"20-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Sublinear Algorithm for Approximate Shortest Paths in Large Networks"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7183-0296","authenticated-orcid":false,"given":"Sabyasachi","family":"Basu","sequence":"first","affiliation":[{"name":"UC Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2557-6166","authenticated-orcid":false,"given":"Nadia","family":"K\u014dshima","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8470-9508","authenticated-orcid":false,"given":"Talya","family":"Eden","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-5964","authenticated-orcid":false,"given":"Omri","family":"Ben-Eliezer","sequence":"additional","affiliation":[{"name":"Technion -- Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2163-3555","authenticated-orcid":false,"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"UC Santa Cruz, Santa Cruz, CA, USA & Amazon, Cupertino, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,3,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Werneck","author":"Abraham Ittai","year":"2011","unstructured":"Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2011a. VC-Dimension and Shortest Path Algorithms. In Automata, Languages and Programming (ICALP '11)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2985473"},{"key":"e_1_3_2_1_3_1","volume-title":"Werneck","author":"Abraham Ittai","year":"2011","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011b. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. In Experimental Algorithms, Panos M. Pardalos and Steffen Rebennack (Eds.)."},{"key":"e_1_3_2_1_4_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 (SIGMOD '13).","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_3_2_1_6_1","volume-title":"Nature","volume":"401","author":"Albert R\u00e9ka","year":"1999","unstructured":"R\u00e9ka Albert, Hawoong Jeong, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 1999. Diameter of the World-Wide Web. Nature, Vol. 401, 6749 (1999)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129121"},{"key":"e_1_3_2_1_8_1","volume-title":"S\u00f8ren Fuglede J\u00f8rgensen, and Kasper Green Larsen","author":"Alon Noga","year":"2023","unstructured":"Noga Alon, Allan Gr\u00f8nlund, S\u00f8ren Fuglede J\u00f8rgensen, and Kasper Green Larsen. 2023. Sublinear Time Shortest Path in Expander Graphs. arxiv: 2307.06113 [cs.DS]"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2019.0742"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3488560.3498383"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3516483"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284359"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.12"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129081"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/050630106"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-019-54206-x"},{"key":"e_1_3_2_1_19_1","volume-title":"Virginia Vassilevska Williams, and Ziqian Zhong","author":"Deng Mingyang","year":"2022","unstructured":"Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong. 2022. New Additive Approximations for Shortest Paths and Cycles (ICALP '22), Vol. 229."},{"key":"e_1_3_2_1_20_1","volume-title":"10th International Workshop, WADS (Lecture Notes in Computer Science)","volume":"4619","author":"Derungs J\u00f6rg","year":"2007","unstructured":"J\u00f6rg Derungs, Riko Jacob, and Peter Widmayer. 2007. Approximate Shortest Paths Guided by a Small Index. In Algorithms and Data Structures, 10th International Workshop, WADS (Lecture Notes in Computer Science), Vol. 4619."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_1_22_1","volume-title":"Virginia Vassilevska Williams, and Tijn de Vos","author":"Dory Michal","year":"2023","unstructured":"Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, and Tijn de Vos. 2023. Fast 2-Approximate All-Pairs Shortest Paths. CoRR, Vol. abs\/2307.09258 (2023)."},{"key":"e_1_3_2_1_23_1","volume-title":"On Power-Law Relationships of the Internet Topology (SIGCOMM '99)","author":"Faloutsos Michalis","year":"1999","unstructured":"Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On Power-Law Relationships of the Internet Topology (SIGCOMM '99)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-4048(93)90100-J"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352070"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065036"},{"key":"e_1_3_2_1_28_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the Shortest Path: A Search Meets Graph Theory (SODA '05)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392745"},{"key":"e_1_3_2_1_30_1","volume-title":"Ramana Rao Kompella, and Ashish Kundu","author":"Jin Xin","year":"2023","unstructured":"Xin Jin, Charalampos Katsis, Fan Sang, Jiahao Sun, Elisa Bertino, Ramana Rao Kompella, and Ashish Kundu. 2023. Prometheus: Infrastructure Security Posture Analysis with AI-generated Attack Graphs. CoRR (2023). showeprint[arXiv]2312.13119"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2008.2011695"},{"key":"e_1_3_2_1_32_1","volume-title":"Tractable Models for Information Diffusion in Social Networks. In Knowledge Discovery in Databases: PKDD","author":"Kimura Masahiro","year":"2006","unstructured":"Masahiro Kimura and Kazumi Saito. 2006. Tractable Models for Information Diffusion in Social Networks. In Knowledge Discovery in Databases: PKDD 2006."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-022-35181-w"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S19-1014"},{"key":"e_1_3_2_1_36_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_1_37_1","volume-title":"Scaling Up Distance Labeling on Graphs with Core-Periphery Properties (SIGMOD '20)","author":"Li Wentao","year":"2020","unstructured":"Wentao Li, Miao Qiao, Lu Qin, Ying Zhang, Lijun Chang, and Xuemin Lin. 2020a. Scaling Up Distance Labeling on Graphs with Core-Periphery Properties (SIGMOD '20)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2020b. Scaling up distance labeling on graphs with core-periphery properties (SIGMOD '20). 1367--1381.","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00694-1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_3_2_1_41_1","unstructured":"Linyuan Lincoln Lu. 2002. Probabilistic methods in massive graphs and Internet computing. Ph.D. Dissertation. University of California San Diego."},{"key":"e_1_3_2_1_42_1","volume-title":"Mohamed Abdur Rahman, and Saleh Basalamah.","author":"Madkour Amgad","year":"2017","unstructured":"Amgad Madkour, Walid G Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, and Saleh Basalamah. 2017. A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044 (2017)."},{"key":"e_1_3_2_1_43_1","first-page":"1","article-title":"The Core Decomposition of Networks: Theory, Algorithms and Applications","volume":"29","author":"Malliaros Fragkiskos D.","year":"2019","unstructured":"Fragkiskos D. Malliaros, Christos Giatsidis, Apostolos N. Papadopoulos, and Michalis Vazirgiannis. 2019. The Core Decomposition of Networks: Theory, Algorithms and Applications. The VLDB Journal, Vol. 29, 1 (nov 2019).","journal-title":"The VLDB Journal"},{"key":"e_1_3_2_1_44_1","series-title":"SIAM Rev","volume-title":"The Structure and Function of Complex Networks","author":"Newman M. E. J.","year":"2003","unstructured":"M. E. J. Newman. 2003. The Structure and Function of Complex Networks. SIAM Rev., Vol. 45, 2 (2003)."},{"key":"e_1_3_2_1_45_1","volume-title":"ESCAPE: Efficiently Counting All 5-Vertex Subgraphs (WWW '17).","author":"Pinar Ali","year":"2017","unstructured":"Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. 2017. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs (WWW '17)."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Ira Pohl. 1969. Bi-directional and heuristic search in path problems. Ph.D. Dissertation. Stanford University USA.","DOI":"10.2172\/1453875"},{"key":"e_1_3_2_1_47_1","unstructured":"Jianzhong Qi Wei Wang Rui Zhang and Zhuowei Zhao. 2020. A Learning Based Approach to Predict Shortest-Path Distances (EBDT'20)."},{"key":"e_1_3_2_1_48_1","volume-title":"Shortest Path Distance Approximation Using Deep Learning Techniques (ASONAM '18)","author":"Rizi Fatemeh Salehi","year":"2020","unstructured":"Fatemeh Salehi Rizi, Joerg Schloetterer, and Michael Granitzer. 2020. Shortest Path Distance Approximation Using Deep Learning Techniques (ASONAM '18)."},{"key":"e_1_3_2_1_49_1","volume-title":"New Algorithms for All Pairs Approximate Shortest Paths (STOC '23)","author":"Roditty Liam","year":"2023","unstructured":"Liam Roditty. 2023. New Algorithms for All Pairs Approximate Shortest Paths (STOC '23)."},{"key":"e_1_3_2_1_50_1","volume-title":"Mucha","author":"Rombach M. Puck","year":"2014","unstructured":"M. Puck Rombach, Mason A. Porter, James H. Fowler, and Peter J. Mucha. 2014. Core-Periphery Structure in Networks. SIAM J. Appl. Math., Vol. 74, 1 (2014)."},{"key":"e_1_3_2_1_51_1","volume-title":"Faster Approximate All Pairs Shortest Paths. CoRR","author":"Saha Barna","year":"2023","unstructured":"Barna Saha and Christopher Ye. 2023. Faster Approximate All Pairs Shortest Paths. CoRR, Vol. abs\/2309.13225 (2023)."},{"key":"e_1_3_2_1_52_1","volume-title":"Social Networks","volume":"5","author":"Seidman Stephen B.","year":"1983","unstructured":"Stephen B. Seidman. 1983. Network structure and minimum degree. Social Networks, Vol. 5, 3 (1983)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00202-1_3"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2013825118"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-012-0262-1"},{"key":"e_1_3_2_1_57_1","volume-title":"Decision Support Systems","volume":"38","author":"Xu Jennifer J","year":"2004","unstructured":"Jennifer J Xu and Hsinchun Chen. 2004. Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks. Decision Support Systems, Vol. 38, 3 (2004)."},{"key":"e_1_3_2_1_58_1","volume-title":"An energy-aware computation offloading method for smart edge computing in wireless metropolitan area networks. Journal of Network and Computer Applications","author":"Xu Xiaolong","year":"2019","unstructured":"Xiaolong Xu, Yuancheng Li, Tao Huang, Yuan Xue, Kai Peng, Lianyong Qi, and Wanchun Dou. 2019. An energy-aware computation offloading method for smart edge computing in wireless metropolitan area networks. Journal of Network and Computer Applications (2019)."},{"key":"e_1_3_2_1_59_1","volume-title":"DEPCOMM: Graph Summarization on System Audit Logs for Attack Investigation. In IEEE Symposium on Security and Privacy (SP).","author":"Xu Zhiqiang","year":"2022","unstructured":"Zhiqiang Xu, Pengcheng Fang, Changlin Liu, Xusheng Xiao, Yu Wen, and Dan Meng. 2022. DEPCOMM: Graph Summarization on System Audit Logs for Attack Investigation. In IEEE Symposium on Security and Privacy (SP)."},{"key":"e_1_3_2_1_60_1","volume-title":"Pruning Based Distance Sketches with Provable Guarantees on Random Graphs (WWW '19)","author":"Zhang Hongyang","year":"2019","unstructured":"Hongyang Zhang, Huacheng Yu, and Ashish Goel. 2019. Pruning Based Distance Sketches with Provable Guarantees on Random Graphs (WWW '19)."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551820"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.032803"},{"key":"e_1_3_2_1_63_1","volume-title":"Zhao","author":"Zhao Xiaohan","year":"2010","unstructured":"Xiaohan Zhao, Alessandra Sala, Christo Wilson, Haitao Zheng, and Ben Y. Zhao. 2010. Orion: Shortest Path Estimation for Large Social Graphs (WOSN'10)."},{"key":"e_1_3_2_1_64_1","volume-title":"7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom).","author":"Zhao Xiaohan","unstructured":"Xiaohan Zhao, Alessandra Sala, Haitao Zheng, and Ben Y. Zhao. 2011. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_3"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"event":{"name":"WSDM '25: The Eighteenth ACM International Conference on Web Search and Data Mining","location":"Hannover Germany","acronym":"WSDM '25","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701551.3703512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3701551.3703512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T09:16:03Z","timestamp":1755767763000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701551.3703512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,10]]},"references-count":66,"alternative-id":["10.1145\/3701551.3703512","10.1145\/3701551"],"URL":"https:\/\/doi.org\/10.1145\/3701551.3703512","relation":{},"subject":[],"published":{"date-parts":[[2025,3,10]]},"assertion":[{"value":"2025-03-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}