{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:32Z","timestamp":1763468252278},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>We study the problem of point-to-point distance querying for massive scale-free graphs, which is important for numerous applications. Given a directed or undirected graph, we propose to build an index for answering such queries based on a novel hop-doubling labeling technique. We derive bounds on the index size, the computation costs and I\/O costs based on the properties of unweighted scale-free graphs. We show that our method is much more efficient and effective compared to the state-of-the-art techniques, in terms of both querying time and indexing costs. Our empirical study shows that our method can handle graphs that are orders of magnitude larger than existing methods.<\/jats:p>","DOI":"10.14778\/2732977.2732993","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1203-1214","source":"Crossref","is-referenced-by-count":61,"title":["Hop doubling label indexing for point-to-point distance querying on scale-free networks"],"prefix":"10.14778","volume":"7","author":[{"given":"Minhao","family":"Jiang","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Ada Wai-Chee","family":"Fu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Yanyan","family":"Xu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/konect.uni-koblenz.de\/networks.  http:\/\/konect.uni-koblenz.de\/networks."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027200"},{"key":"e_1_2_1_3_1","volume-title":"SEA","author":"Abraham I.","year":"2011","unstructured":"I. Abraham , D. Delling , A. V. Goldberg , and R. F. F. Werneck . A hub-based labeling algorithm for shortest paths in road networks . In SEA , 2011 . I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In SEA, 2011."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_8_1","volume-title":"Emergence of scaling in random networks. Science, (286): 509--512","author":"Barabasi A. L.","year":"1999","unstructured":"A. L. Barabasi and R. Albert . Emergence of scaling in random networks. Science, (286): 509--512 , 1999 . A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, (286): 509--512, 1999."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"e_1_2_1_11_1","volume-title":"INFOCOM","author":"Bu T.","year":"2002","unstructured":"T. Bu and D. Towsley . On distinguishing between internet power law topology generators . In INFOCOM , 2002 . T. Bu and D. Towsley. On distinguishing between internet power law topology generators. In INFOCOM, 2002."},{"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.1145\/2390176.2390180"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516417"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2021017.2021025"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380741"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187884"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740673"},{"issue":"026118","key":"e_1_2_1_25_1","first-page":"1","article-title":"Random graphs with arbitrary degree distributions and their applications","volume":"64","author":"Newman M.","year":"2001","unstructured":"M. Newman , S. H. Strogatz , and D. Watts . Random graphs with arbitrary degree distributions and their applications . Physical Review , 64 ( 026118 ): 1 -- 17 , 2001 . M. Newman, S. H. Strogatz, and D. Watts. Random graphs with arbitrary degree distributions and their applications. Physical Review, 64(026118): 1--17, 2001.","journal-title":"Physical Review"},{"key":"e_1_2_1_26_1","volume-title":"Manuale di economia politica con una introduzione alla scienza sociale (manual of political economy)","author":"Pareto V.","year":"1919","unstructured":"V. Pareto . Manuale di economia politica con una introduzione alla scienza sociale (manual of political economy) . Milano : Societa Editrice Libraria , 1919 . V. Pareto. Manuale di economia politica con una introduzione alla scienza sociale (manual of political economy). Milano: Societa Editrice Libraria, 1919."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989368"},{"key":"e_1_2_1_32_1","volume-title":"Complex networks: Small-world, scale-free and beyond","author":"Wang X.","year":"2003","unstructured":"X. Wang and G. Chen . Complex networks: Small-world, scale-free and beyond . IEEE Circuits and Systems Magazine, (First Quarter) : 6--20, 2003 . X. Wang and G. Chen. Complex networks: Small-world, scale-free and beyond. IEEE Circuits and Systems Magazine, (First Quarter): 6--20, 2003."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516418"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732977.2732993","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:22:05Z","timestamp":1672226525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732977.2732993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":34,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.14778\/2732977.2732993"],"URL":"https:\/\/doi.org\/10.14778\/2732977.2732993","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}