{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,28]],"date-time":"2025-12-28T19:13:06Z","timestamp":1766949186308},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,5,9]],"date-time":"2014-05-09T00:00:00Z","timestamp":1399593600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00453-014-9885-5","type":"journal-article","created":{"date-parts":[[2014,5,8]],"date-time":"2014-05-08T15:23:29Z","timestamp":1399562609000},"page":"237-263","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Randomized Partition Trees for Nearest Neighbor Search"],"prefix":"10.1007","volume":"72","author":[{"given":"Sanjoy","family":"Dasgupta","sequence":"first","affiliation":[]},{"given":"Kaushik","family":"Sinha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,9]]},"reference":[{"key":"9885_CR1","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N Ailon","year":"2009","unstructured":"Ailon, N., Chazelle, B.: The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39, 302\u2013322 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9885_CR2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/1327452.1327494","volume":"51","author":"A Andoni","year":"2008","unstructured":"Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1), 117\u2013122 (2008)","journal-title":"Commun. ACM"},{"key":"9885_CR3","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching. J. ACM 45, 891\u2013923 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"9885_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 $${\\mathbb{R}}^n$$ R n . Bull. Soc. Math. France 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"issue":"9","key":"9885_CR5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J Bentley","year":"1975","unstructured":"Bentley, J.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"9885_CR6","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 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"9885_CR7","unstructured":"Cayton, L., Dasgupta, S.: A learning framework for nearest-neighbor search. In: Advances in Neural Information Processing Systems (2007)"},{"key":"9885_CR8","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K Clarkson","year":"1999","unstructured":"Clarkson, K.: Nearest neighbor queries in metric spaces. Discret. Comput. Geom. 22, 63\u201393 (1999)","journal-title":"Discret. Comput. Geom."},{"key":"9885_CR9","volume-title":"Nearest-Neighbor Methods for Learning and Vision: Theory and Practice","author":"K Clarkson","year":"2005","unstructured":"Clarkson, K.: Nearest-neighbor searching and metric space dimensions. In: Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, Cambridge (2005)"},{"key":"9885_CR10","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Freund, Y.: Random projection trees and low dimensional manifolds. In: ACM Symposium on Theory of, Computing, pp. 537\u2013546 (2008)","DOI":"10.1145\/1374376.1374452"},{"key":"9885_CR11","unstructured":"Dasgupta, S., Sinha, K.: Randomized partition trees for exact nearest neighbor search. In: 26th Annual Conference on Learning Theory (2013)"},{"key":"9885_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer, Science, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"9885_CR13","doi-asserted-by":"crossref","unstructured":"Karger, D., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: ACM Symposium on Theory of, Computing, pp. 741\u2013750 (2002)","DOI":"10.1145\/510008.510013"},{"key":"9885_CR14","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Two algorithms for nearest-neighbor search in high dimensions. In: 29th ACM Symposium on Theory of, Computing (1997)","DOI":"10.1145\/258533.258653"},{"key":"9885_CR15","unstructured":"Krauthgamer, R., Lee, J.: Navigating nets: simple algorithms for proximity search. In: ACM-SIAM Symposium on Discrete Algorithms (2004)"},{"key":"9885_CR16","unstructured":"Liu, T., Moore, A., Gray, A., Yang, K.: An investigation of practical approximate nearest neighbor algorithms. In: Advances in Neural Information Processing Systems (2004)"},{"key":"9885_CR17","doi-asserted-by":"crossref","unstructured":"Maneewongvatana, S., Mount, D.: The analysis of a probabilistic approach to nearest neighbor searching. In: Seventh International Worshop on Algorithms and Data Structures, pp. 276\u2013286 (2001)","DOI":"10.1007\/3-540-44634-6_26"},{"key":"9885_CR18","unstructured":"McFee, B., Lanckriet, G.: Large-scale music similarity search with spatial trees. In: 12th Conference of the International Society for Music Retrieval (2011)"},{"key":"9885_CR19","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1214\/aos\/1176343886","volume":"5","author":"C Stone","year":"1977","unstructured":"Stone, C.: Consistent nonparametric regression. Ann. Stat. 5, 595\u2013645 (1977)","journal-title":"Ann. Stat."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9885-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9885-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9885-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T08:51:40Z","timestamp":1565427100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9885-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,9]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9885"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9885-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,9]]}}}