Finding Good Permutants for Searching in Metric Spaces

Karina Figueroa Mora and Rodrigo Paredes

The permutation index has shown to be very effective in medium and high dimensional metric spaces, even in difficult problems, for instance, when solving reverse $k$-nearest neighbor queries. Nevertheless, currently there is no study about which are the desirable features one can ask to a permutant set, or how to select good permutants.

Similar to the case of pivots, our experimental results show that, compared with a randomly chosen set, a good permutant set yields to fast query response or to reduce the amount of space used by the index. In this paper we start by characterizing permutants and studying their discrimination power, and then we propose an effective heuristic to select a good permutant candidate set. We also show empirical evidence that supports our technique.