{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T05:28:27Z","timestamp":1747805307039,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642223501"},{"type":"electronic","value":"9783642223518"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22351-8_16","type":"book-chapter","created":{"date-parts":[[2011,7,18]],"date-time":"2011-07-18T17:46:41Z","timestamp":1311011201000},"page":"255-273","source":"Crossref","is-referenced-by-count":12,"title":["Querying Shortest Path Distance with Bounded Errors in Large Graphs"],"prefix":"10.1007","author":[{"given":"Miao","family":"Qiao","sequence":"first","affiliation":[]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"16_CR1","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01(1), 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"2","key":"16_CR2","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P.E. Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics SSC4\u00a04(2), 100\u2013107 (1968)","journal-title":"IEEE Transactions on Systems Science and Cybernetics SSC4"},{"issue":"5","key":"16_CR3","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/90.958323","volume":"9","author":"P. Francis","year":"2001","unstructured":"Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: IDMaps: A global internet host distance estimation service. IEEE\/ACM Trans. Networking\u00a09(5), 525\u2013540 (2001)","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Ng, E., Zhang, H.: Predicting internet network distance with coordinates-based approaches. In: INFOCOM, pp. 170\u2013179 (2001)","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Shahabi, C., Kolahdouzan, M., Sharifzadeh, M.: A road network embedding technique for k-nearest neighbor search in moving object databases. In: GIS, pp. 94\u2013100 (2002)","DOI":"10.1145\/585147.585167"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: FOCS, pp. 444\u2013453 (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Rattigan, M.J., Maier, M., Jensen, D.: Using structure indices for efficient approximation of network properties. In: KDD, pp. 357\u2013366 (2006)","DOI":"10.1145\/1150402.1150443"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-69497-7_12","volume-title":"Scientific and Statistical Database Management","author":"H.-P. Kriegel","year":"2008","unstructured":"Kriegel, H.-P., Kr\u00f6ger, P., Renz, M., Schmidt, T.: Hierarchical graph embedding for efficient query processing in very large traffic networks. In: Lud\u00e4scher, B., Mamoulis, N. (eds.) SSDBM 2008. LNCS, vol.\u00a05069, pp. 150\u2013167. Springer, Heidelberg (2008)"},{"key":"16_CR9","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"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Gubichev, A., Bedathur, S., 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"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., Gollapudi, S., Najork, M., Panigrahy, R.: A sketch-based distance oracle for web-scale graphs. In: WSDM, pp. 401\u2013410 (2010)","DOI":"10.1145\/1718487.1718537"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Information Processing Letters\u00a070, 39\u201345 (1999)","journal-title":"Information Processing Letters"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1999","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing\u00a020(1), 359\u2013392 (1999)","journal-title":"SIAM Journal on Scientific Computing"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Trans. Knowledge Discovery from Data\u00a01(1) (2007)","DOI":"10.1145\/1217299.1217301"},{"issue":"6","key":"16_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Communications of the ACM\u00a05(6), 345 (1962)","journal-title":"Communications of the ACM"},{"key":"16_CR17","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: SODA, pp. 156\u2013165 (2005)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network database. In: VLDB, pp. 802\u2013813 (2003)","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: VLDB, pp. 840\u2013851 (2004)","DOI":"10.1016\/B978-012088469-8.50074-7"},{"key":"16_CR20","unstructured":"Hu, H., Lee, D.L., Lee, V.C.S.: Distance indexing on road networks. In: VLDB, pp. 894\u2013905 (2006)"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: SIGMOD, pp. 43\u201354 (2008)","DOI":"10.1145\/1376616.1376623"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Wei, F.: TEDI: Efficient shortest path query answering on graphs. In: SIGMOD, pp. 99\u2013110 (2010)","DOI":"10.1145\/1807167.1807181"}],"container-title":["Lecture Notes in Computer Science","Scientific and Statistical Database Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22351-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T04:36:05Z","timestamp":1741322165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22351-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642223501","9783642223518"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22351-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}