{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:27:35Z","timestamp":1768109255445,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2012,4,26]],"date-time":"2012-04-26T00:00:00Z","timestamp":1335398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s00778-012-0274-x","type":"journal-article","created":{"date-parts":[[2012,4,25]],"date-time":"2012-04-25T06:31:06Z","timestamp":1335335466000},"page":"869-888","source":"Crossref","is-referenced-by-count":57,"title":["The exact distance to destination in undirected world"],"prefix":"10.1007","volume":"21","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,4,26]]},"reference":[{"issue":"2","key":"274_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg S., Corneil D.G., Proskurowski A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discret Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discret Methods"},{"key":"274_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barabasi","year":"1999","unstructured":"Barabasi A.-L., Albert R.: Emergence of scaling in random networks. Science. 286, 509\u2013512 (1999)","journal-title":"Science."},{"issue":"4","key":"274_CR3","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S. Baswana","year":"2006","unstructured":"Baswana S., Sen S.: Approximate distance oracles for unweighted graphs in expected o(n2) time. ACM Trans. Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"274_CR4","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender H.L., Koster A.M.C.A: Treewidth computations I. Upper bounds. Inf. Comput. 208(3), 259\u2013275 (2010)","journal-title":"Upper bounds. Inf. Comput."},{"issue":"3","key":"274_CR5","first-page":"212","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"Chaudhuri S., Zaroliagis C.D.: Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica. 27(3), 212\u2013226 (2000)","journal-title":"Part I: Sequential algorithms. Algorithmica."},{"key":"274_CR6","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X.: On-line exact shortest distance query processing. In: Proceedings of EDBT\u201909, pp. 481\u2013492 (2009)","DOI":"10.1145\/1516360.1516417"},{"key":"274_CR7","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of SODA\u201902, pp. 937\u2013946 (2002)"},{"key":"274_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen T.H., Stein C., Rivest R.L., Leiserson C.E.: Introduction to Algorithms. McGraw-Hill Higher Education, USA (2001)"},{"key":"274_CR9","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Gollapudi, S., Najork, M., Panigrahy, R.: A sketch-based distance oracle for web-scale graphs. In: Proceedings of WSDM\u201910, pp. 401\u2013410 (2010)","DOI":"10.1145\/1718487.1718537"},{"issue":"1","key":"274_CR10","first-page":"264","volume":"3","author":"W. Fan","year":"2010","unstructured":"Fan W., Ma S., Tang N., Wu Y., Wu Y.: Graph pattern matching: from intractable to polynomial time. PVLDB 3(1), 264\u2013275 (2010)","journal-title":"PVLDB"},{"key":"274_CR11","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of SODA\u201901, pp. 210\u2013219 (2001)"},{"key":"274_CR12","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: WEA, pp. 319\u2013333. (2008)","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"274_CR13","doi-asserted-by":"crossref","unstructured":"Gou, G., Chirkova, R.: Efficient algorithms for exact ranked twig-pattern matching over graphs. In: Proceedings of SIGMOD\u201908, pp. 581\u2013594 (2008)","DOI":"10.1145\/1376616.1376676"},{"key":"274_CR14","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-hop: a high-compression indexing scheme for reachability query. In: Proceedings of SIGMOD\u201909, pp. 813\u2013826 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"274_CR15","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: Proceedings of SIGMOD\u201908, pp. 595\u2013608 (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"274_CR16","doi-asserted-by":"crossref","unstructured":"Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Proceedings of STACS\u201900, pp. 516\u2013528 (2000)","DOI":"10.1007\/3-540-46541-3_43"},{"key":"274_CR17","doi-asserted-by":"crossref","unstructured":"Li, F., Cheng, D., Hadjieleftheriou, M., Kollios, G., Teng, S.-H.: On trip planning queries in spatial databases. In: Proceedings of SSTD\u201905, pp. 273\u2013290 (2005)","DOI":"10.1007\/11535331_16"},{"key":"274_CR18","doi-asserted-by":"crossref","unstructured":"Liu, L., Wong, R.C.-W.: Finding shortest path on land surface. In: Proceedings of SIGMOD\u201911, pp. 433\u2013444 (2011)","DOI":"10.1145\/1989323.1989369"},{"issue":"3","key":"274_CR19","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"Peleg D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"issue":"7","key":"274_CR20","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1093\/bioinformatics\/bti116","volume":"21","author":"S.A. Rahman","year":"2005","unstructured":"Rahman S.A., Advani P., Schunk R., Schrader R., Schomburg D.: Metabolic pathway analysis web service (pathway hunter tool at cubic). Bioinformatics 21(7), 1189\u20131193 (2005)","journal-title":"Bioinformatics"},{"issue":"2","key":"274_CR21","first-page":"69","volume":"4","author":"M. Rice","year":"2010","unstructured":"Rice M., Tsotras V.J.: Graph indexing of road networks for shortest path queries with label restrictions. PVLDB 4(2), 69\u201380 (2010)","journal-title":"PVLDB"},{"issue":"1","key":"274_CR22","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson N., Seymour P.D.: Graph minors. iii. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"274_CR23","first-page":"4","volume":"33","author":"J. Sankaranarayanan","year":"2010","unstructured":"Sankaranarayanan J., Samet H.: Roads belong in databases. IEEE Data Eng. Bull. 33(2), 4\u201311 (2010)","journal-title":"IEEE Data Eng. Bull."},{"key":"274_CR24","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Hopi: an efficient connection index for complex xml document collections. In: Proceedings of EDBT\u201904, pp. 237\u2013255 (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"274_CR25","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In: Proceedings of ICDE\u201905, pp. 360\u2013371 (2005)"},{"key":"274_CR26","doi-asserted-by":"crossref","unstructured":"Sommer, C., Verbin, E., Yu, W.: Distance oracles for sparse graphs. In: Proceedings of FOCS\u201909, pp. 703\u2013712 (2009)","DOI":"10.1109\/FOCS.2009.27"},{"key":"274_CR27","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of STOC\u201901, pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"},{"key":"274_CR28","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In: Proceedings of SIGMOD\u201911, pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"274_CR29","doi-asserted-by":"crossref","unstructured":"Wei, F.: TEDI: efficient shortest path query answering on graphs. In: Proceedings of SIGMOD\u201910, pp. 99\u2013110 (2010)","DOI":"10.1145\/1807167.1807181"},{"key":"274_CR30","doi-asserted-by":"crossref","unstructured":"Xiao, Y., Wu, W., Pei, J., Wang, W., He, Z.: Efficiently indexing shortest paths by exploiting symmetry in graphs. In: Proceedings of EDBT\u201909, pp. 493\u2013504 (2009)","DOI":"10.1145\/1516360.1516418"},{"issue":"1","key":"274_CR31","first-page":"276","volume":"3","author":"H. Yildirim","year":"2010","unstructured":"Yildirim H., Chaoji V., Zaki M.J.: Grail: scalable reachability index for large graphs. PVLDB 3(1), 276\u2013284 (2010)","journal-title":"PVLDB"},{"key":"274_CR32","doi-asserted-by":"crossref","unstructured":"Yu, J.X., Qin, L., Chang, L.: Keyword Search in Databases. Morgan & Claypool Publishers, San Francisco (2010)","DOI":"10.1007\/978-3-031-79426-1"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0274-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-012-0274-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0274-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T08:19:00Z","timestamp":1687421940000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-012-0274-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,26]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["274"],"URL":"https:\/\/doi.org\/10.1007\/s00778-012-0274-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,26]]}}}