###
Boosting the Permutation Based Index for Proximity Searching

####
Karina Figueroa and Rodrigo Paredes

Proximity searching consists in retrieving objects out of a database
*similar* to a given query.
Nowadays, when multimedia databases are growing up, this is an elementary
task.
The permutation based index (PBI) and its variants are excellent techniques
to solve proximity
searching in high dimensional spaces, however they have been surmountable
in low dimensional ones.
Another PBI's drawback is that the distance between permutations cannot
allow to discard elements safely when solving similarity queries.
In the following, we introduce an improvement on the PBI that allows to
produce a better promissory order using less space than the basic
permutation technique
and also gives us information to discard some elements.
To do so, besides the permutations, we quantize distance information by
defining distance
rings around each permutant, and we also keep this data.
The experimental evaluation shows we can dramatically improve upon
specialized techniques
in low dimensional spaces.
For instance, in the real world dataset of NASA images, our boosted PBI
uses up
to 90% less distances evaluations than AESA, the state-of-the-art
searching
algorithm with the best performance in this particular space.