Quantized ranking for permutation-based indexing

• A Multi-core indexing and searching implementations of our data structure.
• Test our proposal on the full CoPhIR dataset 106-million features.
• Compare our proposal to all the available permutation based indexing technique with larger datasets (1-million and 10-million).
• Compare our proposal to other approximate similarity search techniques like LSH-Forest and AM-Tree.

The K-Nearest Neighbor (K-NN) search problem is the way to find the K closest and most similar objects to a given query. The K-NN is essential for many applications such as information retrieval and visualization, machine learning and data mining. The exponential growth of data imposes to find approximate approaches to this problem. Permutation-based indexing is one of the most recent techniques for approximate similarity search. Objects are represented by permutation lists ordering their distances to a set of selected reference objects, following the idea that two neighboring objects have the same surrounding. In this paper, we propose a novel quantized representation of permutation lists with its related data structure for effective retrieval on single and multicore architectures. Our novel permutation-based indexing strategy is built to be fast, memory efficient and scalable. This is experimentally demonstrated in comparison to existing proposals using several large-scale datasets of millions of documents and of different dimensions.