{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T06:10:33Z","timestamp":1769926233222,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            The emergence of real life graphs with billions of nodes poses significant challenges for managing and querying these graphs. One of the fundamental queries submitted to graphs is the\n            <jats:italic>shortest distance query.<\/jats:italic>\n            Online BFS (breadth-first search) and offline pre-computing pairwise shortest distances are prohibitive in time or space complexity for billion-node graphs. In this paper, we study the feasibility of building\n            <jats:italic>distance oracles<\/jats:italic>\n            for billion-node graphs. A distance oracle provides approximate answers to shortest distance queries by using a pre-computed data structure for the graph. Sketch-based distance oracles are good candidates because they assign each vertex a sketch of bounded size, which means they have linear space complexity. However, state-of-the-art sketch-based distance oracles lack efficiency or accuracy when dealing with big graphs. In this paper, we address the scalability and accuracy issues by focusing on optimizing the three key factors that affect the performance of distance oracles:\n            <jats:italic>landmark selection, distributed BFS<\/jats:italic>\n            , and\n            <jats:italic>answer generation.<\/jats:italic>\n            We conduct extensive experiments on both real networks and synthetic networks to show that we can build distance oracles of affordable cost and efficiently answer shortest distance queries even for billion-node graphs.\n          <\/jats:p>","DOI":"10.14778\/2732219.2732225","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"61-72","source":"Crossref","is-referenced-by-count":33,"title":["Toward a distance oracle for billion-node graphs"],"prefix":"10.14778","volume":"7","author":[{"given":"Zichao","family":"Qi","sequence":"first","affiliation":[{"name":"Tsinghua University Beijing, China"}]},{"given":"Yanghua","family":"Xiao","sequence":"additional","affiliation":[{"name":"Fudan University Shanghai, China"}]},{"given":"Bin","family":"Shao","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/www.worldwidewebsize.com\/.  http:\/\/www.worldwidewebsize.com\/."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/www.facebook.com\/press\/info.php?statistics.  http:\/\/www.facebook.com\/press\/info.php?statistics."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/www.w3.org\/.  http:\/\/www.w3.org\/."},{"key":"e_1_2_1_4_1","volume-title":"Velvet: algorithms for de novo short read assembly using de bruijn graphs.\" Genome Research","author":"Zerbino D. R.","year":"2008","unstructured":"D. R. Zerbino and E. Birney , \" Velvet: algorithms for de novo short read assembly using de bruijn graphs.\" Genome Research , 2008 . D. R. Zerbino and E. Birney, \"Velvet: algorithms for de novo short read assembly using de bruijn graphs.\" Genome Research, 2008."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718537"},{"key":"e_1_2_1_6_1","volume-title":"Fast and scalable analysis of massive social graphs,\" CoRR","author":"Zhao X.","year":"2011","unstructured":"X. Zhao , A. Sala , H. Zheng , and B. Y. Zhao , \" Fast and scalable analysis of massive social graphs,\" CoRR , 2011 . X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao, \"Fast and scalable analysis of massive social graphs,\" CoRR, 2011."},{"key":"e_1_2_1_7_1","volume-title":"Orion: shortest path estimation for large social graphs,\" in WOSN'10","author":"Zhao X.","unstructured":"X. Zhao , A. Sala , C. Wilson , H. Zheng , and B. Y. Zhao , \" Orion: shortest path estimation for large social graphs,\" in WOSN'10 . X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao, \"Orion: shortest path estimation for large social graphs,\" in WOSN'10."},{"key":"e_1_2_1_8_1","author":"Nelder J. A.","year":"1965","unstructured":"J. A. Nelder and R. Mead , \"A simplex method for function minimization,\" Computer Journal , 1965 . J. A. Nelder and R. Mead, \"A simplex method for function minimization,\" Computer Journal, 1965.","journal-title":"\"A simplex method for function minimization,\" Computer Journal"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063834"},{"key":"e_1_2_1_11_1","unstructured":"http:\/\/research.microsoft.com\/en us\/projects\/trinity\/.  http:\/\/research.microsoft.com\/en us\/projects\/trinity\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_13_1","volume-title":"Predicting internet network distance with coordinates-based approaches,\" in INFOCOM'01","author":"Ng T. S. E.","unstructured":"T. S. E. Ng and H. Zhang , \" Predicting internet network distance with coordinates-based approaches,\" in INFOCOM'01 . T. S. E. Ng and H. Zhang, \"Predicting internet network distance with coordinates-based approaches,\" in INFOCOM'01."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030194.1015471"},{"key":"e_1_2_1_15_1","volume-title":"On the curvature of the internet and its usage for overlay construction and distance estimation,\" in INFOCOM '04","author":"Shavitt Y.","unstructured":"Y. Shavitt and T. Tankel , \" On the curvature of the internet and its usage for overlay construction and distance estimation,\" in INFOCOM '04 . Y. Shavitt and T. Tankel, \"On the curvature of the internet and its usage for overlay construction and distance estimation,\" in INFOCOM '04."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"U. Brandes \"A faster algorithm for betweenness centrality \" Journal of Mathematical Sociology 2001.  U. Brandes \"A faster algorithm for betweenness centrality \" Journal of Mathematical Sociology 2001.","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.57"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161100"},{"key":"e_1_2_1_19_1","volume-title":"A space-efficient parallel algorithm for computing betweenness centrality in distributed memory,\" in HIPC'10","author":"Edmonds N.","unstructured":"N. Edmonds , T. Hoefler , and A. Lumsdaine , \" A space-efficient parallel algorithm for computing betweenness centrality in distributed memory,\" in HIPC'10 . N. Edmonds, T. Hoefler, and A. Lumsdaine, \"A space-efficient parallel algorithm for computing betweenness centrality in distributed memory,\" in HIPC'10."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2009.53"},{"key":"e_1_2_1_21_1","volume-title":"Characterizing betweenness centrality algorithm on multi-core architectures,\" in ISPA'09","author":"Tu D.","unstructured":"D. Tu and G. Tan , \" Characterizing betweenness centrality algorithm on multi-core architectures,\" in ISPA'09 . D. Tu and G. Tan, \"Characterizing betweenness centrality algorithm on multi-core architectures,\" in ISPA'09."},{"key":"e_1_2_1_22_1","author":"Ercsey-Ravasz M.","year":"2010","unstructured":"M. Ercsey-Ravasz and Z. Toroczkai , \"Centrality scaling in large networks,\" Phys. Rev. Lett. , 2010 . M. Ercsey-Ravasz and Z. Toroczkai, \"Centrality scaling in large networks,\" Phys. Rev. Lett., 2010.","journal-title":"\"Centrality scaling in large networks,\" Phys. Rev. Lett."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871503"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_28_1","volume-title":"Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters","author":"Leskovec J.","year":"2008","unstructured":"J. Leskovec , K. J. Lang , A. DasGupta , and M. W. Mahoney , \" Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters ,\" 2008 . J. Leskovec, K. J. Lang, A. DasGupta, and M. W. Mahoney, \"Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,\" 2008."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_30_1","volume-title":"R-mat: A recursive model for graph mining,\" in In SDM","author":"Chakrabarti D.","year":"2004","unstructured":"D. Chakrabarti , Y. Zhan , and C. Faloutsos , \" R-mat: A recursive model for graph mining,\" in In SDM , 2004 . D. Chakrabarti, Y. Zhan, and C. Faloutsos, \"R-mat: A recursive model for graph mining,\" in In SDM, 2004."},{"key":"e_1_2_1_31_1","author":"Brandes U.","year":"2007","unstructured":"U. Brandes and C. Pich , \"Centrality estimation in large networks,\" in Special issue \"Complex Networks' Structure and Dynamics\" of the International Journal of Bifurcation and Chaos , 2007 . U. Brandes and C. Pich, \"Centrality estimation in large networks,\" in Special issue \"Complex Networks' Structure and Dynamics\" of the International Journal of Bifurcation and Chaos, 2007.","journal-title":"\"Centrality estimation in large networks,\" in Special issue \"Complex Networks' Structure and Dynamics\" of the International Journal of Bifurcation and Chaos"},{"key":"e_1_2_1_32_1","volume-title":"Approximate distance oracles","author":"Thorup M.","year":"2001","unstructured":"M. Thorup and U. Zwick , \" Approximate distance oracles ,\" 2001 . M. Thorup and U. Zwick, \"Approximate distance oracles,\" 2001."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.29"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_2_1_35_1","volume-title":"Compact routing in power-law graphs,\" in DISC'09","author":"Chen W.","unstructured":"W. Chen , C. Sommer , S.-H. Teng , and Y. Wang , \" Compact routing in power-law graphs,\" in DISC'09 . W. Chen, C. Sommer, S.-H. Teng, and Y. Wang, \"Compact routing in power-law graphs,\" in DISC'09."},{"key":"e_1_2_1_36_1","volume-title":"Reducing maximum stretch in compact routing.\" in INFOCOM'08","author":"Enachescu M.","unstructured":"M. Enachescu , M. Wang , and A. Goel , \" Reducing maximum stretch in compact routing.\" in INFOCOM'08 . M. Enachescu, M. Wang, and A. Goel, \"Reducing maximum stretch in compact routing.\" in INFOCOM'08."},{"key":"e_1_2_1_37_1","volume-title":"Computing the shortest path: A search meets graph theory,\" in SODA '05","author":"Goldberg A. V.","unstructured":"A. V. Goldberg and C. Harrelson , \" Computing the shortest path: A search meets graph theory,\" in SODA '05 . A. V. Goldberg and C. Harrelson, \"Computing the shortest path: A search meets graph theory,\" in SODA '05."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.899021"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9135-9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"L. C. Freeman \"A set of measures of centrality based on betweenness \" Sociometry 1977.  L. C. Freeman \"A set of measures of centrality based on betweenness \" Sociometry 1977.","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_42_1","unstructured":"D. A. Bader S. Kintali K. Madduri and M. Mihail \"Approximating betweenness centrality \" in WAW'07.   D. A. Bader S. Kintali K. Madduri and M. Mihail \"Approximating betweenness centrality \" in WAW'07."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063471"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732219.2732225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:51:27Z","timestamp":1672221087000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732219.2732225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2732219.2732225"],"URL":"https:\/\/doi.org\/10.14778\/2732219.2732225","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}