On the Least Cost for Proximity Searching in Metric Spaces

摘要: Proximity searching consists in retrieving from a database those elements that are similar to query. As the distance is usually expensive compute, goal use as few computations possible satisfy queries. Indexes precomputed distances among speed up such, baseline AESA, which stores all objects, but has been unbeaten query performance for 20 years. In this paper we show it improve upon AESA by using radically different method select promising compare against Our experiments improvements of 75% document databases. We also explore usage our probabilistic algorithm may lose relevant answers. On faces where any exact must examine virtually elements, version obtains 85% correct answers scanning only 10% database.