An Effective Permutant Selection Heuristic for Proximity Searching in
Metric Spaces
Karina Figueroa and Rodrigo Paredes
The permutation based index has shown to be very effective in medium and
high dimensional metric spaces, even in difficult problems such as 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 predictive power;
then we propose an effective heuristic to select a good set of permutant
candidates. We also show empirical evidence that supports our technique.