{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T05:08:15Z","timestamp":1779253695930,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-08-1-1015"],"award-info":[{"award-number":["N00014-08-1-1015"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["HKUST 6184\/04E"],"award-info":[{"award-number":["HKUST 6184\/04E"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0635099"],"award-info":[{"award-number":["CCR-0635099"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,11]]},"abstract":"\n Nearest neighbor searching is the problem of preprocessing a set of\n n<\/jats:italic>\n point points in\n d<\/jats:italic>\n -dimensional space so that, given any query point\n q<\/jats:italic>\n , it is possible to report the closest point to\n q<\/jats:italic>\n rapidly. In approximate nearest neighbor searching, a parameter \u03b5 > 0 is given, and a multiplicative error of (1 + \u03b5) is allowed. We assume that the dimension\n d<\/jats:italic>\n is a constant and treat\n n<\/jats:italic>\n and \u03b5 as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) and query time\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n + 1\/\u03b5\n \n d<\/jats:italic>\n \u22121\n <\/jats:sup>\n ) to high-space solutions having space roughly\n O<\/jats:italic>\n ((\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )\/\u03b5\n \n d<\/jats:italic>\n <\/jats:sup>\n ) and query time\n O<\/jats:italic>\n (log (\n n<\/jats:italic>\n \/\u03b5)).\n <\/jats:p>\n \n We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter \u03b3, where 2 \u2264 \u03b3 \u2264 1\/\u03b5, we show that there exists a data structure of space\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \u03b3\n \n d<\/jats:italic>\n \u22121\n <\/jats:sup>\n log(1\/\u03b5)) that can answer queries in time\n O<\/jats:italic>\n (log(\n n<\/jats:italic>\n \u03b3) + 1\/(\u03b5\u03b3)\n \n (\n d<\/jats:italic>\n \u22121)\/2\n <\/jats:sup>\n . When \u03b3 = 2, this yields a data structure of space\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log (1\/\u03b5)) that can answer queries in time\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n + 1\/\u03b5\n \n (\n d<\/jats:italic>\n \u22121)\/2\n <\/jats:sup>\n ). When \u03b3 = 1\/\u03b5, it provides a data structure of space\n O<\/jats:italic>\n ((\n n<\/jats:italic>\n \/\u03b5\n \n d<\/jats:italic>\n \u22121\n <\/jats:sup>\n )log(1\/\u03b5)) that can answer queries in time\n O<\/jats:italic>\n (log(\n n<\/jats:italic>\n \/\u03b5)).\n <\/jats:p>\n \n Our results are based on a data structure called a (\n t<\/jats:italic>\n ,\u03b5)-AVD, which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to\n t<\/jats:italic>\n representative points of the set, such that for any query point\n q<\/jats:italic>\n in the cell at least one of these points is an approximate nearest neighbor of\n q<\/jats:italic>\n . We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of\n O<\/jats:italic>\n (log (1\/\u03b5)), our space bounds are asymptotically tight in the two extremes, \u03b3 = 2 and \u03b3 = 1\/\u03b5.\n <\/jats:p>","DOI":"10.1145\/1613676.1613677","type":"journal-article","created":{"date-parts":[[2009,11,24]],"date-time":"2009-11-24T15:21:01Z","timestamp":1259076061000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Space-time tradeoffs for approximate nearest neighbor searching"],"prefix":"10.1145","volume":"57","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Kowloon, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theocharis","family":"Malamatos","sequence":"additional","affiliation":[{"name":"University of Peloponnese, Tripoli, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SIBGRAPI.2008.24"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Arya S.","unstructured":"Arya , S. , and Malamatos , T . 2002. Linear-size approximate Voronoi diagrams . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 147--155. Arya, S., and Malamatos, T. 2002. Linear-size approximate Voronoi diagrams. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 147--155."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510011"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Arya S.","unstructured":"Arya , S. , Malamatos , T. , and Mount , D. M . 2005. Space-time tradeoffs for approximate spherical range counting . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 535--544. Arya, S., Malamatos, T., and Mount, D. M. 2005. Space-time tradeoffs for approximate spherical range counting. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 535--544."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132598"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9140-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00022-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/648249.751875"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Conference on Database Theory. 217--235","author":"Beyer K.","unstructured":"Beyer , K. , Goldstein , J. , Ramakrishnan , R. , and Shaft , U. 1999. When is \u201cnearest neighbor\u201d meaningful . In Proceedings of the International Conference on Database Theory. 217--235 . Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is \u201cnearest neighbor\u201d meaningful. In Proceedings of the International Conference on Database Theory. 217--235."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00967115"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009390"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Chan T. M.","year":"2002","unstructured":"Chan , T. M. 2002 . Closest-point problems simplified on the RAM . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 472--473. Chan, T. M. 2002. Closest-point problems simplified on the RAM. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 472--473."},{"key":"e_1_2_1_17_1","unstructured":"Chan T. M. 2006. A minimalist's implementation of an approximate nearest neighbor algorithm in fixed dimensions. Manuscript. (www.cs.vwaterloo.ca\/~tmchan\/sss.ps). Chan T. M. 2006. A minimalist's implementation of an approximate nearest neighbor algorithm in fixed dimensions. Manuscript. (www.cs.vwaterloo.ca\/~tmchan\/sss.ps)."},{"key":"e_1_2_1_18_1","unstructured":"Chan T. M. and Snoeyink J. 1995. Algorithms for approximate nearest-neighbor queries. Manuscript. Chan T. M. and Snoeyink J. 1995. Algorithms for approximate nearest-neighbor queries. Manuscript."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177609"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(74)90120-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1135"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/28905"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002568"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1037"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_2_1_30_1","volume-title":"Matrix Theory","author":"Gantmacher F. R.","unstructured":"Gantmacher , F. R. 1959. Matrix Theory , Volume 2 . Chelsea , New York . Gantmacher, F. R. 1959. Matrix Theory, Volume 2. Chelsea, New York."},{"key":"e_1_2_1_31_1","unstructured":"Golub G. H. and Loan C. F. V. 1996. Matrix Computations 3rd ed. Johns Hopkins University Press Baltimore MD. Golub G. H. and Loan C. F. V. 1996. Matrix Computations 3rd ed. Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875592"},{"key":"e_1_2_1_33_1","unstructured":"Har-Peled S. 2008. Geometric approximation algorithms. (Lecture notes available from http:\/\/valis.cs.uiuc.edu\/~sariel\/teach\/notes\/aprx\/). Har-Peled S. 2008. Geometric approximation algorithms. (Lecture notes available from http:\/\/valis.cs.uiuc.edu\/~sariel\/teach\/notes\/aprx\/)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Krauthgamer R.","unstructured":"Krauthgamer , R. , and Lee , J. R . 2004. Navigating nets: Simple algorithms for proximity search . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 798--807. Krauthgamer, R., and Lee, J. R. 2004. Navigating nets: Simple algorithms for proximity search. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 798--807."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.017"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_41_1","volume-title":"Computational Geometry: An Introduction","author":"Preparata F. P.","year":"1990","unstructured":"Preparata , F. P. , and Shamos , M. I . 1990 . Computational Geometry: An Introduction , 3 rd ed. Springer-Verlag , Berlin, Germany . Preparata, F. P., and Shamos, M. I. 1990. Computational Geometry: An Introduction, 3rd ed. Springer-Verlag, Berlin, Germany.","edition":"3"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.01.007"},{"key":"e_1_2_1_43_1","volume-title":"The Design and Analysis of Spatial Data Structures","author":"Samet H.","unstructured":"Samet , H. 1990. The Design and Analysis of Spatial Data Structures . Addison-Wesley , Reading, MA . Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000114"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1613676.1613677","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1613676.1613677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:08Z","timestamp":1750250468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1613676.1613677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["10.1145\/1613676.1613677"],"URL":"https:\/\/doi.org\/10.1145\/1613676.1613677","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}