{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T23:31:07Z","timestamp":1722987067966},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2013,9,29]],"date-time":"2013-09-29T00:00:00Z","timestamp":1380412800000},"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":[[2014,10]]},"DOI":"10.1007\/s00778-013-0338-6","type":"journal-article","created":{"date-parts":[[2013,9,28]],"date-time":"2013-09-28T08:00:18Z","timestamp":1380355218000},"page":"677-695","source":"Crossref","is-referenced-by-count":5,"title":["Answering exact distance queries on real-world graphs with bounded performance guarantees"],"prefix":"10.1007","volume":"23","author":[{"given":"Yang","family":"Xiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,29]]},"reference":[{"key":"338_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.F.: Hierarchical hub labelings for shortest paths. In: ESA, pp. 24\u201335 (2012)","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"338_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD Conference, pp. 253\u2013262 (1989)","DOI":"10.1145\/66926.66950"},{"issue":"2","key":"338_CR3","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 ak-tree. SIAM J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"338_CR4","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(85)90083-3","volume":"20","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: A new distributed depth-first-search algorithm. Inf. Process. Lett. 20(3), 147\u2013150 (1985)","journal-title":"Inf. Process. Lett."},{"key":"338_CR5","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: LATIN, pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"key":"338_CR6","unstructured":"Bodlaender, H.: Planar graphs with bounded treewidth. Technical Report RUU-CS, (88\u201314) (1988)"},{"key":"338_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: SOFSEM, pp. 1\u201316 (2005)","DOI":"10.1007\/978-3-540-30577-4_1"},{"issue":"2","key":"338_CR8","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, H.L., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"issue":"3","key":"338_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"6","key":"338_CR10","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1007\/s00778-012-0274-x","volume":"21","author":"L Chang","year":"2012","unstructured":"Chang, L., Yu, J.X., Qin, L., Cheng, H., Qiao, M.: The exact distance to destination in undirected world. VLDB J. 21(6), 869\u2013888 (2012)","journal-title":"VLDB J."},{"key":"338_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X.: On-line exact shortest distance query processing. In: EDBT, pp. 481\u2013492 (2009)","DOI":"10.1145\/1516360.1516417"},{"issue":"3\u20134","key":"338_CR12","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V Chepoi","year":"2012","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica 62(3\u20134), 713\u2013732 (2012)","journal-title":"Algorithmica"},{"issue":"5","key":"338_CR13","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, E., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"338_CR14","doi-asserted-by":"crossref","unstructured":"de Montgolfier, F., Soto, M., Viennot, L.:. Treewidth and hyperbolicity of the internet. In: NCA, pp. 25\u201332 (2011)","DOI":"10.1109\/NCA.2011.11"},{"key":"338_CR15","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory. Springer, Berlin (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"issue":"1","key":"338_CR16","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s00453-008-9194-y","volume":"57","author":"FF Dragan","year":"2010","unstructured":"Dragan, F.F., Yan, C.: Collective tree spanners in graphs with bounded parameters. Algorithmica 57(1), 22\u201343 (2010)","journal-title":"Algorithmica"},{"key":"338_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: ESA, pp. 791\u2013802 (2005)","DOI":"10.1007\/11561071_70"},{"issue":"1","key":"338_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"338_CR19","doi-asserted-by":"crossref","unstructured":"Grumbach, S., Wu, Z.: Distributed tree decomposition of graphs and applications to verification. In: Parallel and Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on, pp. 1\u20138. IEEE (2010)","DOI":"10.1109\/IPDPSW.2010.5470828"},{"key":"338_CR20","doi-asserted-by":"crossref","unstructured":"Gubichev, A., Bedathur, S.J., Seufert, S., Weikum, G.: Fast and accurate estimation of shortest paths in large graphs. In: CIKM, pp. 499\u2013508 (2010)","DOI":"10.1145\/1871437.1871503"},{"issue":"4","key":"338_CR21","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1073\/pnas.39.4.315","volume":"39","author":"F Harary","year":"1953","unstructured":"Harary, F., Uhlenbeck, G.: On the number of husimi trees: I. Proc. Natl. Acad. Sci. USA 39(4), 315 (1953)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"2","key":"338_CR22","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"338_CR23","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Xiang, Y., Lee, V.E.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In: SIGMOD Conference, pp. 445\u2013456 (2012)","DOI":"10.1145\/2213836.2213887"},{"issue":"1","key":"338_CR24","first-page":"7","volume":"36","author":"R Jin","year":"2011","unstructured":"Jin, R., Ruan, N., Xiang, Y., Wang, H.: Path-tree: an efficient reachability indexing scheme for large directed graphs. ACM Trans. Database Syst. 36(1), 7 (2011)","journal-title":"ACM Trans. Database Syst."},{"key":"338_CR25","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-hop: a high-compression indexing scheme for reachability query. In: SIGMOD Conference, pp. 813\u2013826 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"338_CR26","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 177\u2013187. ACM (2005)","DOI":"10.1145\/1081870.1081893"},{"issue":"1","key":"338_CR27","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29\u2013123 (2009)","journal-title":"Internet Math."},{"key":"338_CR28","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 135\u2013146. ACM (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"338_CR29","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: WG, pp. 30\u201341 (1999)","DOI":"10.1007\/3-540-46784-X_5"},{"key":"338_CR30","doi-asserted-by":"crossref","unstructured":"Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: CIKM, pp. 867\u2013876 (2009)","DOI":"10.1145\/1645953.1646063"},{"key":"338_CR31","unstructured":"Robertson, N., Seymour, N.: Graph minors. III. planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984)"},{"key":"338_CR32","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Hopi: an efficient connection index for complex xml document collections. In: EDBT, pp. 237\u2013255 (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"issue":"6","key":"338_CR33","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"338_CR34","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: CIKM, pp. 1785\u20131794 (2011)","DOI":"10.1145\/2063576.2063834"},{"key":"338_CR35","doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: SIGMOD Conference, pp. 845\u2013856 (2007)","DOI":"10.1145\/1247480.1247573"},{"key":"338_CR36","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In: SIGMOD Conference, pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"338_CR37","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: answering graph reachability queries in constant time. In: ICDE, p. 75 (2006)"},{"key":"338_CR38","doi-asserted-by":"crossref","unstructured":"Wei, F.: Tedi: efficient shortest path query answering on graphs. In: SIGMOD Conference, pp. 99\u2013110 (2010)","DOI":"10.1145\/1807167.1807181"},{"issue":"2","key":"338_CR39","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.jbi.2011.11.012","volume":"45","author":"Y Xiang","year":"2012","unstructured":"Xiang, Y., James, S.L., Borlawsky, T.B., Huang, K., Payne, P.R.: k-neighborhood decentralization: a comprehensive solution to index the UMLS for large scale knowledge discovery. J. Biomed. Inf. 45(2), 323\u2013336 (2012)","journal-title":"J. Biomed. Inf."},{"issue":"1","key":"338_CR40","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":"338_CR41","unstructured":"Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., Catalyurek, U.: A scalable distributed parallel breadth-first search algorithm on bluegene\/l. In: Supercomputing, 2005. Proceedings of the ACM\/IEEE SC 2005 Conference, pp. 25\u201325. IEEE (2005)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-013-0338-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-013-0338-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-013-0338-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T19:15:22Z","timestamp":1564168522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-013-0338-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,29]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["338"],"URL":"https:\/\/doi.org\/10.1007\/s00778-013-0338-6","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,29]]}}}