{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:59:13Z","timestamp":1781326753116,"version":"3.54.1"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance r(s,t) depends only on labels along the paths from\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose TreeIndex, a novel index method that constructs a resistance distance labelling of size O(n \u2022 h\n                    <jats:sub>G<\/jats:sub>\n                    ) in O(n \u2022 h\n                    <jats:sub>G<\/jats:sub>\n                    <jats:sup>2<\/jats:sup>\n                    \u2022 d\n                    <jats:sub>max<\/jats:sub>\n                    ) time, where h\n                    <jats:sub>G<\/jats:sub>\n                    (tree height) and d\n                    <jats:sub>max<\/jats:sub>\n                    (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in O(h\n                    <jats:sub>G<\/jats:sub>\n                    ) time and single-source queries in O(n \u2022 h\n                    <jats:sub>G<\/jats:sub>\n                    ) time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a 405 GB labelling in 7 hours (single-threaded) and answers exact single-pair queries in 10\n                    <jats:sup>-3<\/jats:sup>\n                    seconds and single-source queries in 190 seconds-the first exact method scalable to such large graphs.\n                  <\/jats:p>","DOI":"10.1145\/3769788","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: A Labelling Approach"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5808-3131","authenticated-orcid":false,"given":"Meihao","family":"Liao","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6542-1087","authenticated-orcid":false,"given":"Yueyang","family":"Pan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8411-2127","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"CAMVIT: Choice routing","unstructured":"2009. CAMVIT: Choice routing. http:\/\/www.camvit.com. Accessed: 2024-06-23."},{"key":"e_1_2_1_2_1","first-page":"782","article-title":"Highway Dimension, Shortest Paths, and Provably Efficient Algorithms","author":"Abraham Ittai","year":"2010","unstructured":"Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck. 2010. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In SODA. 782-793.","journal-title":"SODA."},{"key":"e_1_2_1_3_1","first-page":"349","article-title":"Fast exact shortest-path distance queries on large networks by pruned landmark labeling","author":"Akiba Takuya","year":"2013","unstructured":"Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. 349-360.","journal-title":"SIGMOD."},{"key":"e_1_2_1_4_1","volume-title":"Lap Chi Lau, and Shayan Oveis Gharan","author":"Alev Vedat Levi","year":"2018","unstructured":"Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. In ITCS (LIPIcs, Vol. 94). 41:1-41:16."},{"key":"e_1_2_1_5_1","volume-title":"Mathias B\u00e6k Tejs Knudsen, and Ely Porat","author":"Alstrup Stephen","year":"2016","unstructured":"Stephen Alstrup, S\u00f8ren Dahlgaard, Mathias B\u00e6k Tejs Knudsen, and Ely Porat. 2016. Sublinear Distance Labeling. In ESA (LIPIcs, Vol. 57). 5:1-5:15."},{"key":"e_1_2_1_6_1","first-page":"1442","article-title":"Algorithmic and Hardness Results for the Hub Labeling Problem","author":"Angelidakis Haris","year":"2017","unstructured":"Haris Angelidakis, Yury Makarychev, and Vsevolod Oparin. 2017. Algorithmic and Hardness Results for the Hub Labeling Problem. In SODA. 1442-1461.","journal-title":"SODA."},{"key":"e_1_2_1_7_1","volume-title":"Alternative Route Graphs in Road Networks. In ICST Conference, TAPAS (Lecture Notes in Computer Science","volume":"32","author":"Bader Roland","year":"2011","unstructured":"Roland Bader, Jonathan Dees, Robert Geisberger, and Peter Sanders. 2011. Alternative Route Graphs in Road Networks. In ICST Conference, TAPAS (Lecture Notes in Computer Science, Vol. 6595). 21-32."},{"key":"e_1_2_1_8_1","volume-title":"32nd International Workshop. 1-14","author":"Bodlaender Hans L.","year":"2006","unstructured":"Hans L. Bodlaender. 2006. Treewidth: Characterizations, Applications, and Computations. In Graph-Theoretic Concepts in Computer Science, 32nd International Workshop. 1-14."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"e_1_2_1_10_1","first-page":"174","article-title":"An Empirical Comparison of Graph Laplacian Solvers","author":"Boman Erik G.","year":"2016","unstructured":"Erik G. Boman, Kevin Deweese, and John R. Gilbert. 2016. An Empirical Comparison of Graph Laplacian Solvers. In ALENEX. 174-188.","journal-title":"ALENEX."},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"Effective Resistances in Non-Expander Graphs","volume":"274","author":"Cai Dongrun","year":"2023","unstructured":"Dongrun Cai, Xue Chen, and Pan Peng. 2023. Effective Resistances in Non-Expander Graphs. In ESA, Vol. 274. 29:1-29:18.","journal-title":"ESA"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0274-x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1380624"},{"key":"e_1_2_1_14_1","first-page":"313","article-title":"P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators","author":"Chen Zitong","year":"2021","unstructured":"Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang. 2021. P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators. In SIGMOD. 313-325.","journal-title":"SIGMOD."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/568547.568553"},{"key":"e_1_2_1_17_1","first-page":"16","article-title":"Polylog-time and near-linear work approximation scheme for undirected shortest paths","author":"Cohen Edith","year":"1994","unstructured":"Edith Cohen. 1994. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In STOC. 16-26.","journal-title":"STOC."},{"key":"e_1_2_1_18_1","first-page":"937","article-title":"Reachability and distance queries via 2-hop labels","author":"Cohen Edith","year":"2002","unstructured":"Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2002. Reachability and distance queries via 2-hop labels. In SODA. 937-946.","journal-title":"SODA."},{"key":"e_1_2_1_19_1","first-page":"343","article-title":"Solving SDD linear systems in nearly mlog1\/2n time","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly mlog1\/2n time. In STOC. 343-352.","journal-title":"STOC."},{"key":"e_1_2_1_20_1","first-page":"962","article-title":"Fast and Compact Exact Distance Oracle for Planar Graphs","author":"Cohen-Addad Vincent","year":"2017","unstructured":"Vincent Cohen-Addad, S\u00f8ren Dahlgaard, and Christian Wulff-Nilsen. 2017. Fast and Compact Exact Distance Oracle for Planar Graphs. In FOCS. 962-973.","journal-title":"FOCS."},{"key":"e_1_2_1_21_1","first-page":"148","article-title":"An Optimality Theorem for a Bi-Directional Heuristic Search","volume":"20","author":"de Champeaux Dennis","year":"1977","unstructured":"Dennis de Champeaux and Lenie Sint. 1977. An Optimality Theorem for a Bi-Directional Heuristic Search Algorithm. Comput. J. 20, 2 (1977), 148-150.","journal-title":"Algorithm. Comput. J."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Camil Demetrescu Andrew Goldberg and David Johnson. 2009. The shortest path problem: Ninth DIMACS implementation challenge. https:\/\/www.diag.uniroma1.it\/challenge9.","DOI":"10.1090\/dimacs\/074"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1361328"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2024.01.012"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Rajat Vadiraj Dwaraknath Ishani Karmarkar and Aaron Sidford. 2023. Towards Optimal Effective Resistance Estimation. In NIPS.","DOI":"10.52202\/075280-2575"},{"key":"e_1_2_1_26_1","first-page":"128","article-title":"Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths","author":"Elkin Michael","year":"2016","unstructured":"Michael Elkin and Ofer Neiman. 2016. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. In FOCS. 128-137.","journal-title":"FOCS."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626731"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709685"},{"key":"e_1_2_1_29_1","first-page":"268","article-title":"Compact Navigation and Distance Oracles for Graphs with Small Treewidth","author":"Farzan Arash","year":"2011","unstructured":"Arash Farzan and Shahin Kamali. 2011. Compact Navigation and Distance Oracles for Graphs with Small Treewidth. In ICALP. 268-280.","journal-title":"ICALP."},{"key":"e_1_2_1_30_1","first-page":"457","article-title":"IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying","volume":"6","author":"Wai-Chee Fu Ada","year":"2013","unstructured":"Ada Wai-Chee Fu, Huanhuan Wu, James Cheng, and Raymond Chi-Wing Wong. 2013. IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying. VLDB 6, 6 (2013), 457-468.","journal-title":"VLDB"},{"key":"e_1_2_1_31_1","volume-title":"Spielman","author":"Gao Yuan","year":"2023","unstructured":"Yuan Gao, Rasmus Kyng, and Daniel A. Spielman. 2023. Robust and Practical Solution of Laplacian Equations by Approximate Elimination. CoRR abs\/2303.00709 (2023)."},{"key":"e_1_2_1_32_1","first-page":"210","article-title":"Distance labeling in graphs","author":"Gavoille Cyril","year":"2001","unstructured":"Cyril Gavoille, David Peleg, Stephane Perennes, and Ran Raz. 2001. Distance labeling in graphs. In SODA. 210-219.","journal-title":"SODA."},{"key":"e_1_2_1_33_1","first-page":"156","article-title":"Computing the shortest path: A search meets graph theory","author":"Goldberg Andrew V.","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In SODA. 156-165.","journal-title":"SODA."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond","volume":"132","author":"Gupta Siddharth","year":"2019","unstructured":"Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. 2019. Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. In ICALP, Vol. 132. 143:1-143:15.","journal-title":"ICALP"},{"key":"e_1_2_1_36_1","first-page":"3733","article-title":"Efficient Algorithms for Spanning Tree Centrality","author":"Hayashi Takanori","year":"2016","unstructured":"Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. In IJCAI. 3733-3739.","journal-title":"IJCAI."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01154-8"},{"key":"e_1_2_1_38_1","first-page":"540","article-title":"Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers","author":"Jambulapati Arun","year":"2021","unstructured":"Arun Jambulapati and Aaron Sidford. 2021. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. In SODA. 540-559.","journal-title":"SODA."},{"key":"e_1_2_1_39_1","first-page":"1203","article-title":"Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks","volume":"7","author":"Jiang Minhao","year":"2014","unstructured":"Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, and Yanyan Xu. 2014. Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks. VLDB 7, 12 (2014), 1203-1214.","journal-title":"VLDB"},{"key":"e_1_2_1_40_1","first-page":"477","article-title":"Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks","author":"Koehler Henning","year":"2025","unstructured":"Henning Koehler, Muhammad Farhan, and Qing Wang. 2025. Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks. In EDBT. 477-489.","journal-title":"EDBT."},{"key":"e_1_2_1_41_1","first-page":"1462","article-title":"Beyond Highway Dimension","author":"Kosowski Adrian","year":"2017","unstructured":"Adrian Kosowski and Laurent Viennot. 2017. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. In SODA. 1462-1478.","journal-title":"Small Distance Labels Using Tree Skeletons. In SODA."},{"key":"e_1_2_1_42_1","first-page":"573","article-title":"Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. In FOCS. 573-582.","journal-title":"FOCS."},{"key":"e_1_2_1_43_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford. edu\/data."},{"key":"e_1_2_1_44_1","first-page":"2728","article-title":"A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs","author":"Li Lawrence","year":"2023","unstructured":"Lawrence Li and Sushant Sachdeva. 2023. A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. In SODA. 2728-2745.","journal-title":"SODA."},{"key":"e_1_2_1_45_1","first-page":"1367","article-title":"Scaling Up Distance Labeling on Graphs with Core-Periphery Properties","author":"Li Wentao","year":"2020","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. 1367-1381.","journal-title":"SIGMOD."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709686"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588922"},{"key":"e_1_2_1_48_1","volume-title":"Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach. Full version: https:\/\/www.arxiv.org\/abs\/2509.05129","author":"Liao Meihao","year":"2025","unstructured":"Meihao Liao, Yueyang Pan, Rong-Hua Li, and Guoren Wang. 2025. Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach. Full version: https:\/\/www.arxiv.org\/abs\/2509.05129 (2025)."},{"key":"e_1_2_1_49_1","first-page":"133","article-title":"Efficient and Provable Effective Resistance Computation on Large Graphs","volume":"2","author":"Liao Meihao","year":"2024","unstructured":"Meihao Liao, Junjie Zhou, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, and Guoren Wang. 2024. Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach. Proc. ACM Manag. Data 2, 3 (2024), 133.","journal-title":"An Index-based Approach. Proc. ACM Manag. Data"},{"key":"e_1_2_1_50_1","first-page":"221","article-title":"CurvDrop: A Ricci Curvature Based Approach to Prevent Graph Neural Networks from Over-Smoothing and Over-Squashing","author":"Liu Yang","year":"2023","unstructured":"Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. 2023. CurvDrop: A Ricci Curvature Based Approach to Prevent Graph Neural Networks from Over-Smoothing and Over-Squashing. In WWW. 221-230.","journal-title":"WWW."},{"key":"e_1_2_1_51_1","first-page":"1023","article-title":"Computing Personalized PageRank Quickly by Exploiting Graph Structures","volume":"7","author":"Maehara Takanori","year":"2014","unstructured":"Takanori Maehara, Takuya Akiba, Yoichi Iwata, and Ken-ichi Kawarabayashi. 2014. Computing Personalized PageRank Quickly by Exploiting Graph Structures. VLDB 7, 12 (2014), 1023-1034.","journal-title":"VLDB"},{"key":"e_1_2_1_52_1","first-page":"383","article-title":"Measuring the mixing time of social graphs","author":"Mohaisen Abedelaziz","year":"2010","unstructured":"Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. 2010. Measuring the mixing time of social graphs. In SIGCOMM. 383-389.","journal-title":"SIGCOMM."},{"key":"e_1_2_1_53_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_54_1","first-page":"709","article-title":"When Hierarchy Meets 2-Hop-Labeling","author":"Ouyang Dian","year":"2018","unstructured":"Dian Ouyang, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. 2018. When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks. In SIGMOD. 709-724.","journal-title":"Efficient Shortest Distance Queries on Road Networks. In SIGMOD."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx021"},{"key":"e_1_2_1_57_1","first-page":"1329","article-title":"Local Algorithms for Estimating Effective Resistance","author":"Peng Pan","year":"2021","unstructured":"Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. 2021. Local Algorithms for Estimating Effective Resistance. In KDD. 1329-1338.","journal-title":"KDD."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxaa150"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_60_1","first-page":"315","article-title":"A Simple and Efficient Parallel Laplacian Solver","author":"Sachdeva Sushant","year":"2023","unstructured":"Sushant Sachdeva and Yibin Zhao. 2023. A Simple and Efficient Parallel Laplacian Solver. In SPAA. 315-325.","journal-title":"SPAA."},{"key":"e_1_2_1_61_1","first-page":"99","article-title":"Density-based place clustering in geo-social networks","author":"Shi Jieming","year":"2014","unstructured":"Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W. Cheung. 2014. Density-based place clustering in geo-social networks. In SIGMOD. 99-110.","journal-title":"SIGMOD."},{"key":"e_1_2_1_62_1","first-page":"282","article-title":"Robust Routing Using Electrical Flows","author":"Sinop Ali Kemal","year":"2021","unstructured":"Ali Kemal Sinop, Lisa Fawcett, Sreenivas Gollapudi, and Kostas Kollias. 2021. Robust Routing Using Electrical Flows. In SIGSPATIAL. 282-292.","journal-title":"SIGSPATIAL."},{"key":"e_1_2_1_63_1","first-page":"563","article-title":"Graph sparsification by effective resistances","author":"Spielman Daniel A.","year":"2008","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In STOC. 563-568.","journal-title":"STOC."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_2_1_65_1","volume-title":"Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein.","author":"Topping Jake","year":"2022","unstructured":"Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR."},{"key":"e_1_2_1_66_1","first-page":"99","article-title":"TEDI: efficient shortest path query answering on graphs","author":"Wei Fang","year":"2010","unstructured":"Fang Wei. 2010. TEDI: efficient shortest path query answering on graphs. In SIGMOD. 99-110.","journal-title":"SIGMOD."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588696"},{"key":"e_1_2_1_68_1","first-page":"896","article-title":"Challenging the Long Tail Recommendation","volume":"5","author":"Yin Hongzhi","year":"2012","unstructured":"Hongzhi Yin, Bin Cui, Jing Li, Junjie Yao, and Chen Chen. 2012. Challenging the Long Tail Recommendation. VLDB 5, 9 (2012), 896-907.","journal-title":"VLDB"},{"key":"e_1_2_1_69_1","first-page":"336","article-title":"Dynamic Hub Labeling for Road Networks","author":"Zhang Mengxuan","year":"2021","unstructured":"Mengxuan Zhang, Lei Li, Wen Hua, Rui Mao, Pingfu Chao, and Xiaofang Zhou. 2021. Dynamic Hub Labeling for Road Networks. In ICDE. 336-347.","journal-title":"ICDE."},{"key":"e_1_2_1_70_1","first-page":"1992","article-title":"Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks","author":"Zhang Yikai","year":"2022","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2022. Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks. In SIGMOD. 1992-2005.","journal-title":"SIGMOD."},{"key":"e_1_2_1_71_1","first-page":"1678","article-title":"Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks","author":"Zheng Bolong","year":"2023","unstructured":"Bolong Zheng, Yong Ma, Jingyi Wan, Yongyong Gao, Kai Huang, Xiaofang Zhou, and Christian S. Jensen. 2023. Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks. In ICDE. 1678-1690.","journal-title":"ICDE."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:52:40Z","timestamp":1781326360000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":71,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769788"],"URL":"https:\/\/doi.org\/10.1145\/3769788","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}