On the Least Cost For Proximity Searching in Metric Spaces

Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes

Proximity searching consists in retrieving from a database those elements that are similar to a query. As the distance is usually expensive to compute, the goal is to use as few distance computations as possible to satisfy queries. Indexes use precomputed distances among database elements to speed up queries. As such, a baseline is AESA, which stores all the distances among database objects, but has been unbeaten in query performance for 20 years. In this paper we show that it is possible to improve upon AESA by using a radically different method to select the promising database elements to compare against the query. Our experiments show improvements of up to 25% in documents databases.