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