Efficient search supporting several similarity queries by reordering pivots

Abstract

Effective similarity search indexing in general metric spaces has traditionally received special attention in several areas of interest like pattern recognition, computer vision or information retrieval. A typical method is based on the use of a distance as a dissimilarity function (not restricting to Euclidean distance) where the main objective is to speed up the search of the most similar object in a database by minimising the number of distance computations. Several types of search can be defined, being the k-nearest neigh-bour or the range search the most common. AESA is one of the most well known of such algorithms due to its performance (measured in distance computations). PiAESA is an AESA variant where the main objective has changed. Instead of trying to find the best nearest neighbour candidate at each step, it tries to find the object that contributes the most to have a bigger lower bound function, that is, a better estimation of the distance. In this paper we extend and test PiAESA to support several similarity queries. Our empirical results show that this approach obtains a significant improvement in performance when comparing with competing algorithms.