{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T04:16:19Z","timestamp":1780719379584,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>We study the problem of computing shortest path or distance between two query vertices in a graph, which has numerous important applications. Quite a number of indexes have been proposed to answer such distance queries. However, all of these indexes can only process graphs of size barely up to 1 million vertices, which is rather small in view of many of the fast-growing real-world graphs today such as social networks and Web graphs. We propose an efficient index, which is a novel labeling scheme based on the independent set of a graph. We show that our method can handle graphs of size orders of magnitude larger than existing indexes.<\/jats:p>","DOI":"10.14778\/2536336.2536346","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"457-468","source":"Crossref","is-referenced-by-count":77,"title":["IS-Label"],"prefix":"10.14778","volume":"6","author":[{"given":"Ada Wai-Chee","family":"Fu","sequence":"first","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huanhuan","family":"Wu","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, Hong Kong University of Science &amp; Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"690","volume-title":"ICALP (1)","author":"Abraham I.","year":"2011","unstructured":"I. Abraham , D. Delling , A. Fiat , A. V. Goldberg , and R. F. F. Werneck . Vc-dimension and shortest path algorithms . In ICALP (1) , pages 690 - 699 , 2011 . I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. Vc-dimension and shortest path algorithms. In ICALP (1), pages 690-699, 2011."},{"key":"e_1_2_1_2_1","first-page":"230","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 , pages 230 - 241 , 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, pages 230-241, 2011."},{"key":"e_1_2_1_3_1","first-page":"24","volume-title":"Proceedings of the 20th Annual European Conference on Algorithms (ESA)","author":"Abraham I.","year":"2012","unstructured":"I. Abraham , D. Delling , A. V. Goldberg , and R. F. F. Werneck . Hierarchical hub labelings for shortest paths . In Proceedings of the 20th Annual European Conference on Algorithms (ESA) , pages 24 - 35 , 2012 . I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of the 20th Annual European Conference on Algorithms (ESA), pages 24-35, 2012."},{"key":"e_1_2_1_4_1","first-page":"782","volume-title":"SODA","author":"Abraham I.","year":"2010","unstructured":"I. Abraham , A. Fiat , A. V. Goldberg , and R. F. F. Werneck . Highway dimension, shortest paths, and provably efficient algorithms . In SODA , pages 782 - 793 , 2010 . I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In SODA, pages 782-793, 2010."},{"issue":"9","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The input\/output complexity of sorting and related problems","volume":"31","author":"Aggarwal A.","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter . The input\/output complexity of sorting and related problems . Commun. ACM , 31 ( 9 ): 1116 - 1127 , 1988 . A. Aggarwal and J. S. Vitter. The input\/output complexity of sorting and related problems. Commun. ACM, 31(9):1116-1127, 1988.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/1109557.1109623","volume-title":"SODA","author":"Ajwani D.","year":"2006","unstructured":"D. Ajwani , R. Dementiev , and U. Meyer . A computational study of external-memory BFS algorithms . In SODA , pages 601 - 610 , 2006 . D. Ajwani, R. Dementiev, and U. Meyer. A computational study of external-memory BFS algorithms. In SODA, pages 601-610, 2006."},{"key":"e_1_2_1_7_1","volume-title":"ALENEX","author":"Ajwani D.","year":"2007","unstructured":"D. Ajwani , U. Meyer , and V. Osipov . Improved external memory bfs implementation . In ALENEX , 2007 . D. Ajwani, U. Meyer, and V. Osipov. Improved external memory bfs implementation. In ALENEX, 2007."},{"issue":"4","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","article-title":"Approximate distance oracles for unweighted graphs in expected o(n2) time","volume":"2","author":"Baswana S.","year":"2006","unstructured":"S. Baswana and S. Sen . Approximate distance oracles for unweighted graphs in expected o(n2) time . ACM Transactions on Algorithms , 2 ( 4 ): 557 - 577 , 2006 . S. Baswana and S. Sen. Approximate distance oracles for unweighted graphs in expected o(n2) time. ACM Transactions on Algorithms, 2(4):557-577, 2006.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_2_1_9_1","first-page":"15","article-title":"Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm","author":"Bauer R.","year":"2010","unstructured":"R. Bauer , D. Delling , P. Sanders , D. Schieferdecker , D. Schultes , and D. Wagner . Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm . ACM Journal of Experimental Algorithmics , 15 , 2010 . R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm. ACM Journal of Experimental Algorithmics, 15, 2010.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_2_1_10_1","volume-title":"INFOCOM","author":"Bu T.","year":"2002","unstructured":"T. Bu and D. F. Towsley . On distinguishing between internet power law topology generators . In INFOCOM , 2002 . T. Bu and D. F. Towsley. On distinguishing between internet power law topology generators. In INFOCOM, 2002."},{"key":"e_1_2_1_11_1","first-page":"859","volume-title":"SODA","author":"Buchsbaum A. L.","year":"2000","unstructured":"A. L. Buchsbaum , M. H. Goldwasser , S. Venkatasubramanian , and J. Westbrook . On external memory graph traversal . In SODA , pages 859 - 860 , 2000 . A. L. Buchsbaum, M. H. Goldwasser, S. Venkatasubramanian, and J. Westbrook. On external memory graph traversal. In SODA, pages 859-860, 2000."},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"The VLDB Journal","author":"Chang L.","year":"2012","unstructured":"L. Chang , J. Yu , L. Qin , H. Cheng , and M. Qiao . The exact distance to destination in undirected world . The VLDB Journal , pages 1 - 20 , 2012 (Online First). L. Chang, J. Yu, L. Qin, H. Cheng, and M. Qiao. The exact distance to destination in undirected world. The VLDB Journal, pages 1-20, 2012 (Online First)."},{"key":"e_1_2_1_13_1","first-page":"457","volume-title":"SIGMOD Conference","author":"Cheng J.","year":"2012","unstructured":"J. Cheng , Y. Ke , S. Chu , and C. Cheng . Efficient processing of distance queries in large graphs: a vertex cover approach . In SIGMOD Conference , pages 457 - 468 , 2012 . J. Cheng, Y. Ke, S. Chu, and C. Cheng. Efficient processing of distance queries in large graphs: a vertex cover approach. In SIGMOD Conference, pages 457-468, 2012."},{"issue":"11","key":"e_1_2_1_14_1","first-page":"1292","article-title":"Who is in your small world","volume":"5","author":"Cheng J.","year":"2012","unstructured":"J. Cheng , Z. Shang , H. Cheng , H. Wang , and J. X. Yu . K-reach : Who is in your small world . PVLDB , 5 ( 11 ): 1292 - 1303 , 2012 . J. Cheng, Z. Shang, H. Cheng, H. Wang, and J. X. Yu. K-reach: Who is in your small world. PVLDB, 5(11):1292-1303, 2012.","journal-title":"PVLDB"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/1516360.1516417","volume-title":"EDBT","author":"Cheng J.","year":"2009","unstructured":"J. Cheng and J. X. Yu . On-line exact shortest distance query processing . In EDBT , pages 481 - 492 , 2009 . J. Cheng and J. X. Yu. On-line exact shortest distance query processing. In EDBT, pages 481-492, 2009."},{"issue":"5","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539702403098","article-title":"Reachability and distance queries via 2-hop labels","volume":"32","author":"Cohen E.","year":"2003","unstructured":"E. Cohen , E. Halperin , H. Kaplan , and U. Zwick . Reachability and distance queries via 2-hop labels . SIAM J. Comput. , 32 ( 5 ): 1338 - 1355 , 2003 . E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5):1338-1355, 2003.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_17_1","volume-title":"Is-label: an independent-set labeling scheme for point-to-point distance querying on large graphs. arXiv:1211.2367","author":"Fu A. W.-C.","year":"2012","unstructured":"A. W.-C. Fu , H. Wu , J. Cheng , S. Cho , and R. C.-W. Wong . Is-label: an independent-set labeling scheme for point-to-point distance querying on large graphs. arXiv:1211.2367 , 2012 . A. W.-C. Fu, H. Wu, J. Cheng, S. Cho, and R. C.-W. Wong. Is-label: an independent-set labeling scheme for point-to-point distance querying on large graphs. arXiv:1211.2367, 2012."},{"key":"e_1_2_1_18_1","first-page":"319","volume-title":"WEA","author":"Geisberger R.","year":"2008","unstructured":"R. Geisberger , P. Sanders , D. Schultes , and D. Delling . Contraction hierarchies: Faster and simpler hierarchical routing in road networks . In WEA , pages 319 - 333 , 2008 . R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA, pages 319-333, 2008."},{"key":"e_1_2_1_19_1","first-page":"156","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Goldberg A. V.","year":"2005","unstructured":"A. V. Goldberg and C. Harrelson . Computing the shortest path: A* search meets graph theory . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 156 - 165 , 2005 . A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 156-165, 2005."},{"key":"e_1_2_1_20_1","first-page":"499","volume-title":"CIKM","author":"Gubichev A.","year":"2010","unstructured":"A. Gubichev , S. J. Bedathur , S. Seufert , and G. Weikum . Fast and accurate estimation of shortest paths in large graphs . In CIKM , pages 499 - 508 , 2010 . A. Gubichev, S. J. Bedathur, S. Seufert, and G. Weikum. Fast and accurate estimation of shortest paths in large graphs. In CIKM, pages 499-508, 2010."},{"issue":"1","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02523693","article-title":"Greed is good: Approximating independent sets in sparse and bounded-degree graphs","volume":"18","author":"Halld\u00f3rsson M. M.","year":"1997","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan . Greed is good: Approximating independent sets in sparse and bounded-degree graphs . Algorithmica , 18 ( 1 ): 145 - 163 , 1997 . M. M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1):145-163, 1997.","journal-title":"Algorithmica"},{"key":"e_1_2_1_22_1","article-title":"Engineering multilevel overlay graphs for shortest-path queries","author":"Holzer M.","year":"2008","unstructured":"M. Holzer , F. Schulz , and D. Wagner . Engineering multilevel overlay graphs for shortest-path queries . ACM Journal of Experimental Algorithmics, 13(2.5) , 2008 . M. Holzer, F. Schulz, and D. Wagner. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics, 13(2.5), 2008.","journal-title":"ACM Journal of Experimental Algorithmics, 13(2.5)"},{"key":"e_1_2_1_23_1","first-page":"445","volume-title":"SIGMOD Conference","author":"Jin R.","year":"2012","unstructured":"R. Jin , N. Ruan , Y. Xiang , and V. E. Lee . A highway-centric labeling approach for answering distance queries on large sparse graphs . In SIGMOD Conference , pages 445 - 456 , 2012 . R. Jin, N. Ruan, Y. Xiang, and V. E. Lee. A highway-centric labeling approach for answering distance queries on large sparse graphs. In SIGMOD Conference, pages 445-456, 2012."},{"key":"e_1_2_1_24_1","first-page":"169","volume-title":"IEEE Symp. on Parallel and Distributed Processing","author":"Kumar V.","year":"1996","unstructured":"V. Kumar and E. J. Schwabe . Improved algorithms and data structures for solving graph problems in external memory . In IEEE Symp. on Parallel and Distributed Processing , pages 169 - 177 , 1996 . V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In IEEE Symp. on Parallel and Distributed Processing, pages 169-177, 1996."},{"key":"e_1_2_1_25_1","first-page":"723","volume-title":"ESA","author":"Mehlhorn K.","year":"2002","unstructured":"K. Mehlhorn and U. Meyer . External-memory breadth-first search with sublinear I\/O . In ESA , pages 723 - 735 , 2002 . K. Mehlhorn and U. Meyer. External-memory breadth-first search with sublinear I\/O. In ESA, pages 723-735, 2002."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-642-03456-5_15","volume-title":"Efficient Algorithms","author":"Meyer U.","year":"2009","unstructured":"U. Meyer . Via detours to I\/O-efficient shortest paths . In Efficient Algorithms , pages 219 - 232 , 2009 . U. Meyer. Via detours to I\/O-efficient shortest paths. In Efficient Algorithms, pages 219-232, 2009."},{"key":"e_1_2_1_27_1","first-page":"85","volume-title":"ALENEX","author":"Meyer U.","year":"2009","unstructured":"U. Meyer and V. Osipov . Design and implementation of a practical i\/o-efficient shortest paths algorithm . In ALENEX , pages 85 - 96 , 2009 . U. Meyer and V. Osipov. Design and implementation of a practical i\/o-efficient shortest paths algorithm. In ALENEX, pages 85-96, 2009."},{"key":"e_1_2_1_28_1","first-page":"540","volume-title":"ESA","author":"Meyer U.","year":"2006","unstructured":"U. Meyer and N. Zeh . I\/O-efficient undirected shortest paths with unbounded edge lengths . In ESA , pages 540 - 551 , 2006 . U. Meyer and N. Zeh. I\/O-efficient undirected shortest paths with unbounded edge lengths. In ESA, pages 540-551, 2006."},{"key":"e_1_2_1_29_1","first-page":"687","volume-title":"SODA","author":"Munagala K.","year":"1999","unstructured":"K. Munagala and A. G. Ranade . I\/o-complexity of graph algorithms . In SODA , pages 687 - 694 , 1999 . K. Munagala and A. G. Ranade. I\/o-complexity of graph algorithms. In SODA, pages 687-694, 1999."},{"key":"e_1_2_1_30_1","first-page":"867","volume-title":"CIKM","author":"Potamias M.","year":"2009","unstructured":"M. Potamias , F. Bonchi , C. Castillo , and A. Gionis . Fast shortest path distance estimation in large networks . In CIKM , pages 867 - 876 , 2009 . M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. Fast shortest path distance estimation in large networks. In CIKM, pages 867-876, 2009."},{"key":"e_1_2_1_31_1","first-page":"43","volume-title":"SIGMOD Conference","author":"Samet H.","year":"2008","unstructured":"H. Samet , J. Sankaranarayanan , and H. Alborzi . Scalable network distance browsing in spatial databases . In SIGMOD Conference , pages 43 - 54 , 2008 . H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In SIGMOD Conference, pages 43-54, 2008."},{"key":"e_1_2_1_32_1","first-page":"568","volume-title":"ESA","author":"Sanders P.","year":"2005","unstructured":"P. Sanders and D. Schultes . Highway hierarchies hasten exact shortest path queries . In ESA , pages 568 - 579 , 2005 . P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In ESA, pages 568-579, 2005."},{"issue":"1","key":"e_1_2_1_33_1","first-page":"1210","article-title":"Path oracles for spatial networks","volume":"2","author":"Sankaranarayanan J.","year":"2009","unstructured":"J. Sankaranarayanan , H. Samet , and H. Alborzi . Path oracles for spatial networks . PVLDB , 2 ( 1 ): 1210 - 1221 , 2009 . J. Sankaranarayanan, H. Samet, and H. Alborzi. Path oracles for spatial networks. PVLDB, 2(1):1210-1221, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_34_1","first-page":"401","volume-title":"WSDM","author":"Sarma A. D.","year":"2010","unstructured":"A. D. Sarma , S. Gollapudi , M. Najork , and R. Panigrahy . A sketch-based distance oracle for web-scale graphs . In WSDM , pages 401 - 410 , 2010 . A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. A sketch-based distance oracle for web-scale graphs. In WSDM, pages 401-410, 2010."},{"key":"e_1_2_1_35_1","first-page":"237","volume-title":"EDBT","author":"Schenkel R.","year":"2004","unstructured":"R. Schenkel , A. Theobald , and G. Weikum . Hopi: An efficient connection index for complex xml document collections . In EDBT , pages 237 - 255 , 2004 . R. Schenkel, A. Theobald, and G. Weikum. Hopi: An efficient connection index for complex xml document collections. In EDBT, pages 237-255, 2004."},{"key":"e_1_2_1_36_1","first-page":"43","volume-title":"SIGMOD Conference","author":"Tao Y.","year":"2011","unstructured":"Y. Tao , C. Sheng , and J. Pei . On k-skip shortest paths . In SIGMOD Conference , pages 43 - 54 , 2011 . Y. Tao, C. Sheng, and J. Pei. On k-skip shortest paths. In SIGMOD Conference, pages 43-54, 2011."},{"issue":"1","key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","article-title":"Approximate distance oracles","volume":"52","author":"Thorup M.","year":"2005","unstructured":"M. Thorup and U. Zwick . Approximate distance oracles . J. ACM , 52 ( 1 ): 1 - 24 , 2005 . M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005.","journal-title":"J. ACM"},{"issue":"6684","key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of 'small-world' networks","volume":"393","author":"Watts D.","year":"1998","unstructured":"D. Watts and S. Strogatz . Collective dynamics of 'small-world' networks . Nature , 393 ( 6684 ): 440 - 442 , 1998 . D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440-442, 1998.","journal-title":"Nature"},{"key":"e_1_2_1_39_1","first-page":"99","volume-title":"SIGMOD Conference","author":"Wei F.","year":"2010","unstructured":"F. Wei . Tedi : efficient shortest path query answering on graphs . In SIGMOD Conference , pages 99 - 110 , 2010 . F. Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD Conference, pages 99-110, 2010."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1145\/1516360.1516418","volume-title":"EDBT","author":"Xiao Y.","year":"2009","unstructured":"Y. Xiao , W. Wu , J. Pei , W. Wang , and Z. He . Efficiently indexing shortest paths by exploiting symmetry in graphs . In EDBT , pages 493 - 504 , 2009 . Y. Xiao, W. Wu, J. Pei, W. Wang, and Z. He. Efficiently indexing shortest paths by exploiting symmetry in graphs. In EDBT, pages 493-504, 2009."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536336.2536346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:42:58Z","timestamp":1672224178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536336.2536346"}},"subtitle":["an independent-set based labeling scheme for point-to-point distance querying"],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.14778\/2536336.2536346"],"URL":"https:\/\/doi.org\/10.14778\/2536336.2536346","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,4]]}}}