A hybrid approach to boost the permutation index for similarity searching

Abstract

We propose a hybrid strategy that combines three ideas, namely, a convenient way for reducing the length of the permutations, using a permutation similarity measure adjusted for these clipped permutations, and the use of the closest permutant of each object as a pivot for it. In this way, we increase the discriminability of the permutation index in order to reduce even more the number of distance computations without reducing the answer quality. The performance of our proposal is tested using two classical real-world databases: NASA and Colors which are part of the SISAP project’s metric space benchmark. We reduced more than 30% of the number of distance evaluations needed to solve the queries on both databases.