ompact and Efficient Permutations for Proximity Searching
Karina Figueroa Mora and Rodrigo Paredes
Proximity searching consists in retrieving the most similar objects
to a given query. This kind of searching is a basic tool in many fields
of artificial intelligence, because it can be used as a search engine
to solve problems like kNN searching. A common technique to solve
proximity queries is to use an index. In this paper, we show a variant
of the permutation based index, which, in his original version, has a great
predicting power about which are the objects worth to compare with the query
(avoiding the exhaustive comparison).
We have noted that when two permutants are close, they can produce
small differences in the order in which objects are revised, which could
be responsible of finding the true answer or missing it.
In this paper we pretend to mitigate this effect. As a matter of fact,
our technique allows us both to reduce the index size and to improve the
query cost up to 30%.