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 promising database elements to compare against the
query. Our experiments show improvements of up to 75% in document databases.
We also explore the usage of our method as a probabilistic algorithm that may
lose relevant answers. On a database of faces where any exact algorithm must
examine virtually all elements, our probabilistic version obtains 85% of the
correct answers by scanning only 10% of the database.