Candidate List Obtained from Metric Inverted Index for Similarity Searching

Similarity searching consists of retrieving the most similar elements in a database. This is a central problem in many real applications, and it becomes intractable when a big database is used. A way to overcome this problem is by getting a few objects as a promissory candidate list of being part of the answer. In this paper, the most relevant and efficient algorithms for high dimensional spaces based on the permutations-technique are compared. Permutation-based algorithm is related to make a permutation of some special objects that allows us to organize the space of the elements in a database. One of the indexes related uses a complete permutation, and the second one utilizes a small part of the permutation and an inverted index.