Permutation’s Signatures for Proximity Searching in Metric Spaces

In a multimedia database, similarity searching is the only significant way to retrieve the most similar objects to a given query. The usual approach to efficiently solve this kind of search is building an index, which allows reducing the response time of online queries. Recently, the permutation-based algorithms (PBA) were presented, and from then on, this technique has been very successful. A PBA index consists of storing the permutation of any database element with respect to a set of permutants. If the cardinality of the set of permutants is \(\beta \), any permutation needs storing a sequence of \(\beta \) small integers, whose values are between 1 to \(\beta \). However, if we have space restrictions over the index, the only way of reducing its size is by considering fewer permutants. Hence, the index performance could be severely affected.