{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:34Z","timestamp":1750307614038,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of A Coru\u00f1a, Spain","award":["TIN2006-15071-C03-03"],"award-info":[{"award-number":["TIN2006-15071-C03-03"]}]},{"name":"Millennium Institute for Cell Dynamics and Biotechnology","award":["ICM P05-001-F"],"award-info":[{"award-number":["ICM P05-001-F"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            Proximity searching consists of retrieving from a database those elements that are similar to a query object. The usual model for proximity searching is a metric space where the distance, which models the proximity, is expensive to compute. An index uses precomputed distances to speedup query processing. Among all the known indices, the baseline for performance for about 20 years has been AESA. This index uses an iterative procedure, where at each iteration it first chooses the next promising element (\u201cpivot\u201d) to compare to the query, and then it discards database elements that can be proved not relevant to the query using the pivot. The next pivot in AESA is chosen as the one minimizing the sum of lower bounds to the distance to the query proved by previous pivots. In this article, we introduce the new index\n            <jats:italic>iAESA<\/jats:italic>\n            , which establishes a new performance baseline for metric space searching. The difference with AESA is the method to select the next pivot. In iAESA, each candidate sorts previous pivots by closeness to it, and chooses the next pivot as the candidate whose order is most similar to that of the query. We also propose a modification to AESA-like algorithms to turn them into probabilistic algorithms.\n          <\/jats:p>\n          <jats:p>Our empirical results confirm a consistent improvement in query performance. For example, we perform as few as 60% of the distance evaluations of AESA in a database of documents, a very important and difficult real-life instance of the problem. For the probabilistic algorithm, we perform in a database of faces up to 40% of the comparisons made by the best alternative algorithm to retrieve the same percentage of the correct answer. Based on the empirical results, we conjecture that the new probabilistic AESA-like algorithms will become, as AESA had been for exact algorithms, a reference point establishing, in practice, a lower bound on how good a probabilistic proximity search algorithm can be.<\/jats:p>","DOI":"10.1145\/1498698.1564506","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":7,"title":["Speeding up spatial approximation search in metric spaces"],"prefix":"10.1145","volume":"14","author":[{"given":"Karina","family":"Figueroa","sequence":"first","affiliation":[{"name":"Universidad Michoacana, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edgar","family":"Chavez","sequence":"additional","affiliation":[{"name":"Universidad Michoacana\/CICESE, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo","family":"Paredes","sequence":"additional","affiliation":[{"name":"University of Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"volume-title":"Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94)","author":"Arya S.","unstructured":"Arya , S. , Mount , D. , Netanyahu , N. , Silverman , R. , and Wu , A . 1994. An optimal algorithm for approximate nearest neighbor searching in fixed dimension . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94) . ACM, New York, 573--583. Arya, S., Mount, D., Netanyahu, N., Silverman, R., and Wu, A. 1994. An optimal algorithm for approximate nearest neighbor searching in fixed dimension. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA'94). ACM, New York, 573--583.","key":"e_1_2_1_1_1"},{"volume-title":"Modern Information Retrieval","author":"Baeza-Yates R.","unstructured":"Baeza-Yates , R. and Ribeiro-Neto , B. 1999. Modern Information Retrieval . Addison-Wesley , New York . Baeza-Yates, R. and Ribeiro-Neto, B. 1999. Modern Information Retrieval. Addison-Wesley, New York.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/502807.502809"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/S1570-8667(03)00067-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/TPAMI.2007.70815"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/S0020-0190(02)00344-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/j.patrec.2004.11.014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/502807.502808"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/582410.582412"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/PL00009449"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1137\/S0895480102412856"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1016\/j.patrec.2006.06.012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/958942.958948"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/0167-8655(96)00032-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/0167-8655(94)90095-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1142\/S0218001402002003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/j.datak.2007.05.002"},{"volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06)","author":"Paredes R.","unstructured":"Paredes , R. and Navarro , G . 2006. Optimal incremental sorting . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06) . SIAM, Philadelphia, 171--182. Paredes, R. and Navarro, G. 2006. Optimal incremental sorting. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). SIAM, Philadelphia, 171--182.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/j.jda.2008.09.014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/S0262-8856(97)00070-X"},{"volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet H.","unstructured":"Samet , H. 2006. Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann , New York . Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, New York.","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0167-8655(86)90013-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/0020-0190(95)00161-X"},{"unstructured":"White D. and Jain R. 1996. Algorithms and strategies for similarity retrieval. Tech. rep. VCL-96-101 Visual Computing Laboratory University of California.  White D. and Jain R. 1996. Algorithms and strategies for similarity retrieval. Tech. rep. VCL-96-101 Visual Computing Laboratory University of California.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","volume-title":"Advances in Database Systems","volume":"32","author":"Zezula P.","unstructured":"Zezula , P. , Amato , G. , Dohnal , V. , and Batko , M . 2006. Similarity search: the metric space approach . Advances in Database Systems , vol. 32 . Springer, Berlin. Zezula, P., Amato, G., Dohnal, V., and Batko, M. 2006. Similarity search: the metric space approach. Advances in Database Systems, vol. 32. Springer, Berlin."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1564506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1564506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1564506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":25,"alternative-id":["10.1145\/1498698.1564506"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1564506","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}