{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:06:28Z","timestamp":1755839188571,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"crossref","award":["UOA1732"],"award-info":[{"award-number":["UOA1732"]}],"id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003524","name":"Ministry of Business, Innovation and Employment","doi-asserted-by":"publisher","award":["3721519"],"award-info":[{"award-number":["3721519"]}],"id":[{"id":"10.13039\/501100003524","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ARC","award":["DP180103096 and FT170100128","FT200100787"],"award-info":[{"award-number":["DP180103096 and FT170100128","FT200100787"]}]},{"name":"ARC","award":["DP160101513, FT180100256"],"award-info":[{"award-number":["DP160101513, FT180100256"]}]},{"name":"NSFC, ARC","award":["NSFC61232006, 2018YFB1003504, ARC DP200101338, DP180103096, DP170101628"],"award-info":[{"award-number":["NSFC61232006, 2018YFB1003504, ARC DP200101338, DP180103096, DP170101628"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00778-021-00694-1","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T09:03:51Z","timestamp":1630400631000},"page":"129-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Distance labeling: on parallelism, compression, and ordering"],"prefix":"10.1007","volume":"31","author":[{"given":"Wentao","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"694_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1681\u20131697. SIAM (2014)","DOI":"10.1137\/1.9781611973730.112"},{"key":"694_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: European Symposium on Algorithms, pp. 24\u201335. Springer (2012)","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"694_CR3","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Kawarabayashi, K., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In: 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 147\u2013154. SIAM (2014)","DOI":"10.1137\/1.9781611973198.14"},{"key":"694_CR4","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349\u2013360. ACM (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"694_CR5","doi-asserted-by":"crossref","unstructured":"Akiba, T., Sommer, C., Kawarabayashi, K.: Shortest-path queries for complex networks: exploiting low tree-width outside the core. In: Proceedings of the 15th International Conference on Extending Database Technology, pp. 144\u2013155. ACM (2012)","DOI":"10.1145\/2247596.2247614"},{"key":"694_CR6","doi-asserted-by":"crossref","unstructured":"AlGhamdi, Z., Jamour, F., Skiadopoulos, S., Kalnis, P.: A benchmark for betweenness centrality approximation algorithms on large graphs. In: Proceedings of the 29th International Conference on Scientific and Statistical Database Management, pp. 1\u201312 (2017)","DOI":"10.1145\/3085504.3085510"},{"key":"694_CR7","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Kintali, S., Madduri, K., Mihail, M.: Approximating betweenness centrality. In: International Workshop on Algorithms and Models for the Web-Graph, pp. 124\u2013137. Springer (2007)","DOI":"10.1007\/978-3-540-77004-6_10"},{"key":"694_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M.P., Bertino, E., Kumar, R. (eds.) Proceedings of the 20th International Conference on World Wide Web, pp. 587\u2013596. ACM Press (2011)","DOI":"10.1145\/1963405.1963488"},{"key":"694_CR9","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The webgraph framework I: compression techniques. In: Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004), pp. 595\u2013601. ACM Press, Manhattan, USA (2004)","DOI":"10.1145\/988672.988752"},{"key":"694_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.entcs.2016.03.005","volume":"322","author":"M Borassi","year":"2016","unstructured":"Borassi, M., Crescenzi, P., Habib, M.: Into the square: on the complexity of some quadratic-time solvable problems. Electron. Notes Theor. Comput. Sci. 322, 51\u201367 (2016)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"1","key":"694_CR11","first-page":"1","volume":"24","author":"M Borassi","year":"2019","unstructured":"Borassi, M., Natale, E.: KADABRA is an adaptive algorithm for betweenness via random approximation. J. Exp. Algorithmics (JEA) 24(1), 1\u201335 (2019)","journal-title":"J. Exp. Algorithmics (JEA)"},{"issue":"4","key":"694_CR12","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.socnet.2005.11.005","volume":"28","author":"SP Borgatti","year":"2006","unstructured":"Borgatti, S.P., Everett, M.G.: A graph-theoretic perspective on centrality. Soc. Netw. 28(4), 466\u2013484 (2006)","journal-title":"Soc. Netw."},{"issue":"2","key":"694_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001)","journal-title":"J. Math. Sociol."},{"issue":"2","key":"694_CR14","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.socnet.2007.11.001","volume":"30","author":"U Brandes","year":"2008","unstructured":"Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136\u2013145 (2008)","journal-title":"Soc. Netw."},{"issue":"1","key":"694_CR15","first-page":"4","volume":"9","author":"W Chen","year":"2012","unstructured":"Chen, W., Sommer, C., Teng, S.-H., Wang, Y.: A compact routing scheme and approximate distance oracle for power-law graphs. ACM Trans. Algorithms (TALG) 9(1), 4 (2012)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"694_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/971617.971643","volume":"47","author":"T Coffman","year":"2004","unstructured":"Coffman, T., Greenblatt, S., Marcus, S.: Graph-based technologies for intelligence analysis. Commun. ACM 47(3), 45\u201347 (2004)","journal-title":"Commun. ACM"},{"key":"694_CR17","doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937\u2013946. Society for Industrial and Applied Mathematics (2002)","DOI":"10.1137\/S0097539702403098"},{"issue":"4","key":"694_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1734213.1734219","volume":"57","author":"S Dolev","year":"2010","unstructured":"Dolev, S., Elovici, Y., Puzis, R.: Routing betweenness centrality. J. ACM (JACM) 57(4), 1\u201327 (2010)","journal-title":"J. ACM (JACM)"},{"key":"694_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40, 35\u201341 (1977)","journal-title":"Sociometry"},{"issue":"6","key":"694_CR20","doi-asserted-by":"publisher","first-page":"457","DOI":"10.14778\/2536336.2536346","volume":"6","author":"AWC Fu","year":"2013","unstructured":"Fu, A.W.C., Wu, H., Cheng, J., Wong, R.C.W.: Is-label: an independent-set based labeling scheme for point-to-point distance querying. Proc. VLDB Endow. 6(6), 457\u2013468 (2013)","journal-title":"Proc. VLDB Endow."},{"issue":"22","key":"694_CR21","doi-asserted-by":"publisher","first-page":"7794","DOI":"10.1073\/pnas.0407994102","volume":"102","author":"R Guimera","year":"2005","unstructured":"Guimera, R., Mossa, S., Turtschi, A., Amaral, L.A.N.: The worldwide air transportation network: anomalous centrality, community structure, and cities global roles. Proc. Natl. Acad. Sci. 102(22), 7794\u20137799 (2005)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"694_CR22","doi-asserted-by":"crossref","unstructured":"Hayashi, T., Akiba, T., Kawarabayashi, K.: Fully dynamic shortest-path distance query acceleration on massive networks. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 1533\u20131542. ACM (2016)","DOI":"10.1145\/2983323.2983731"},{"key":"694_CR23","doi-asserted-by":"crossref","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: The Collected Works of Wassily Hoeffding, pp. 409\u2013426. Springer (1994)","DOI":"10.1007\/978-1-4612-0865-5_26"},{"key":"694_CR24","doi-asserted-by":"crossref","unstructured":"Jacob, R., Kosch\u00fctzki, D., Lehmann, K.A., Peeters, L., Tenfelde-Podehl, D.: Algorithms for centrality indices. In: Network Analysis, pp. 62\u201382. Springer (2005)","DOI":"10.1007\/978-3-540-31955-9_4"},{"issue":"6833","key":"694_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong, H., Mason, S.P., Barab\u00e1si, A.-L., Oltvai, Z.N.: Lethality and centrality in protein networks. Nature 411(6833), 41\u201342 (2001)","journal-title":"Nature"},{"issue":"12","key":"694_CR26","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.14778\/2732977.2732993","volume":"7","author":"M Jiang","year":"2014","unstructured":"Jiang, M., Fu, A.W.C., Wong, R.C.W., Xu, Y.: Hop doubling label indexing for point-to-point distance querying on scale-free networks. Proc. VLDB Endow. 7(12), 1203\u20131214 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"694_CR27","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: Konect: the koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343\u20131350. ACM (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"694_CR28","unstructured":"Jure, L., Andrej, K.: SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data, June (2014)"},{"key":"694_CR29","doi-asserted-by":"crossref","unstructured":"Li, J., Wang, X., Deng, K., Yang, X., Sellis, T., Yu, J.X.: Most influential community search over large social networks. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 871\u2013882. IEEE (2017)","DOI":"10.1109\/ICDE.2017.136"},{"key":"694_CR30","doi-asserted-by":"crossref","unstructured":"Li, W., Qiao, M., Qin, L., Zhang, Y., Chang, L., Lin, X.: Scaling distance labeling on small-world networks. In: Proceedings of the 2019 International Conference on Management of Data, pp. 1060\u20131077 (2019)","DOI":"10.1145\/3299869.3319877"},{"issue":"4","key":"694_CR31","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/3186728.3164141","volume":"11","author":"Y Li","year":"2017","unstructured":"Li, Y., Leong Hou, U., Yiu, M.L., Kou, N.M., et al.: An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow. 11(4), 445\u2013457 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"6840","key":"694_CR32","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1038\/35082140","volume":"411","author":"F Liljeros","year":"2001","unstructured":"Liljeros, F., Edling, C.R., Amaral, L.A., Stanley, H.E., \u00c5berg, Y.: The web of human sexual contacts. Nature 411(6840), 907\u2013908 (2001)","journal-title":"Nature"},{"key":"694_CR33","doi-asserted-by":"crossref","unstructured":"Ouyang, D., Qin, L., Chang, L., Lin, X., Zhang, Y., Zhu, Q.: When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In: Proceedings of the 2018 International Conference on Management of Data, pp. 709\u2013724. ACM (2018)","DOI":"10.1145\/3183713.3196913"},{"key":"694_CR34","doi-asserted-by":"crossref","unstructured":"Pfeffer, J., Carley, K.M.: k-centralities: local approximations of global measures based on shortest paths. In: Proceedings of the 21st International Conference on World Wide Web, pp. 1043\u20131050 (2012)","DOI":"10.1145\/2187980.2188239"},{"key":"694_CR35","doi-asserted-by":"crossref","unstructured":"Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, pp. 867\u2013876. ACM (2009)","DOI":"10.1145\/1645953.1646063"},{"issue":"1","key":"694_CR36","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/TKDE.2012.253","volume":"26","author":"M Qiao","year":"2014","unstructured":"Qiao, M., Cheng, H., Chang, L., Yu, J.X.: Approximate shortest distance computing: a query-dependent local landmark scheme. IEEE Trans. Knowl. Data Eng. 26(1), 55\u201368 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"694_CR37","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/s10618-015-0423-0","volume":"30","author":"M Riondato","year":"2016","unstructured":"Riondato, M., Kornaropoulos, E.M.: Fast approximation of betweenness centrality through sampling. Data Min. Knowl. Disc. 30(2), 438\u2013475 (2016)","journal-title":"Data Min. Knowl. Disc."},{"issue":"5","key":"694_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3208351","volume":"12","author":"M Riondato","year":"2018","unstructured":"Riondato, M., Upfal, E.: Abra: approximating betweenness centrality in static and dynamic graphs with rademacher averages. ACM Trans. Knowl. Disc. Data (TKDD) 12(5), 1\u201338 (2018)","journal-title":"ACM Trans. Knowl. Disc. Data (TKDD)"},{"key":"694_CR39","doi-asserted-by":"crossref","unstructured":"Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"694_CR40","unstructured":"Polina, R., Aris, A., Aristides, G., Nikolaj, T.: Event detection in activity networks. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1176\u20131185. ACM (2014)"},{"key":"694_CR41","doi-asserted-by":"crossref","unstructured":"Shen, C.Y., Huang, L.H., Yang, D.N., Shuai, H.H., Lee, W.C., Chen, M.S.: On finding socially tenuous groups for online social networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 415\u2013424. ACM (2017)","DOI":"10.1145\/3097983.3097995"},{"issue":"4","key":"694_CR42","doi-asserted-by":"publisher","first-page":"449","DOI":"10.14778\/2735496.2735507","volume":"8","author":"M Then","year":"2014","unstructured":"Then, M., Kaufmann, M., Chirigati, F., Hoang-Vu, T.-A., Pham, K., Kemper, A., Neumann, T., Vo, H.T.: The more the merrier: efficient multi-source graph traversal. Proc. VLDB Endow. 8(4), 449\u2013460 (2014)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"694_CR43","first-page":"61","volume":"1","author":"J Travers","year":"1967","unstructured":"Travers, J., Milgram, S.: The small world problem. Psychol. Today 1(1), 61\u201367 (1967)","journal-title":"Psychol. Today"},{"key":"694_CR44","doi-asserted-by":"crossref","unstructured":"Tretyakov, K., Armas-Cervantes, A., Garc\u00eda-Ba\u00f1uelos, L., Vilo, J., Dumas, M.: Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pp. 1785\u20131794. ACM (2011)","DOI":"10.1145\/2063576.2063834"},{"key":"694_CR45","doi-asserted-by":"crossref","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440 (1998)","DOI":"10.1038\/30918"},{"key":"694_CR46","doi-asserted-by":"crossref","unstructured":"Wei, F.: TEDI: efficient shortest path query answering on graphs. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 99\u2013110. ACM (2010)","DOI":"10.1145\/1807167.1807181"},{"issue":"5","key":"694_CR47","doi-asserted-by":"publisher","first-page":"406","DOI":"10.14778\/2140436.2140438","volume":"5","author":"L Wu","year":"2012","unstructured":"Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. Proc. VLDB Endow. 5(5), 406\u2013417 (2012)","journal-title":"Proc. VLDB Endow."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00694-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00694-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00694-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T09:44:01Z","timestamp":1673171041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00694-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["694"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00694-1","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"assertion":[{"value":"3 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}