{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:09:18Z","timestamp":1743152958416,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540877431"},{"type":"electronic","value":"9783540877448"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_10","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"112-123","source":"Crossref","is-referenced-by-count":3,"title":["Space-Time Tradeoffs for Proximity Searching in Doubling Spaces"],"prefix":"10.1007","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Vigneron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T.: Linear-size approximate Voronoi diagrams. In: Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, pp. 147\u2013155 (2002)","DOI":"10.1145\/509907.510011"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Space-efficient approximate Voronoi diagrams. In: Proc. 34th Annu. ACM Sympos. Theory Comput., pp. 721\u2013730 (2002)","DOI":"10.1145\/509907.510011"},{"key":"10_CR3","unstructured":"Arya, S., Mount, D.M., Netanyahu, N., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In: Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pp. 573\u2013582 (1994)"},{"issue":"4","key":"10_CR4","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans \u211d n . Bull. Soc. Math. France\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"10_CR6","unstructured":"Brin, S.: Near neighbor search in large metric spaces. In: Proc. 21st International Conf. on Very Large Data Bases, pp. 574\u2013584 (1995)"},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. Assoc. Comput. Mach.\u00a042, 67\u201390 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom.\u00a022(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.: Searching dynamic point sets in spaces with bounded doubling dimension. In: Proc. 38th Annu. ACM Sympos. Theory Comput., pp. 574\u2013583 (2006)","DOI":"10.1145\/1132516.1132599"},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0167-8655(82)90025-3","volume":"1","author":"C.D. Feustel","year":"1982","unstructured":"Feustel, C.D., Shapiro, L.G.: The nearest neighbor problem in an abstract metric space. Pattern Recognition Letters\u00a01(2), 125\u2013128 (1982)","journal-title":"Pattern Recognition Letters"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proc. 44th Annu. IEEE Sympos. Found. Comput. Sci., pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pp. 94\u2013103 (2001)","DOI":"10.1109\/SFCS.2001.959884"},{"issue":"5","key":"10_CR13","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput.\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: Proc. 34th Annu. ACM Sympos. Theory Comput., pp. 741\u2013750 (2002)","DOI":"10.1145\/509907.510013"},{"key":"10_CR15","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 798\u2013807 (2004)"},{"issue":"2-3","key":"10_CR16","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/j.tcs.2005.09.017","volume":"348","author":"R. Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R.: The black-box complexity of nearest-neighbor search. Theoretical Computer Science\u00a0348(2-3), 262\u2013276 (2005)","journal-title":"Theoretical Computer Science"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: Proc. 47th Annu. IEEE Sympos. Found. Comput. Sci., pp. 119\u2013132 (2006)","DOI":"10.1109\/FOCS.2006.9"},{"key":"10_CR18","unstructured":"Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pp. 311\u2013321 (1993)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:05:26Z","timestamp":1738350326000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}