Vincent Gripon's Homepage

Research and Teaching Blog

Memory vectors for similarity search in high-dimensional spaces

A. Iscen, T. Furon, V. Gripon, M. Rabbat and H. Jégou, "Memory vectors for similarity search in high-dimensional spaces," in IEEE Transactions on Big Data, pp. 1--13, 2017.

We study an indexing architecture to store and search in a database of high-dimensional vectors from the perspective of statistical signal processing and decision theory. This architecture is composed of several memory units, each of which summarizes a fraction of the database by a single representative vector. The potential similarity of the query to one of the vectors stored in the memory unit is gauged by a simple correlation with the memory unit’s representative vector. This representative optimizes the test of the following hypothesis: the query is independent from any vector in the memory unit vs. the query is a simple perturbation of one of the stored vectors. Compared to exhaustive search, our approach finds the most similar database vectors significantly faster without a noticeable reduction in search quality. Interestingly, the reduction of complexity is provably better in high-dimensional spaces. We empirically demonstrate its practical interest in a large-scale image search scenario with off-the-shelf state-of-the-art descriptors.


Bibtex
@article{IscFurGriRabJé2017,
  author = {Ahmet Iscen and Teddy Furon and Vincent
Gripon and Michael Rabbat and Hervé Jégou},
  title = {Memory vectors for similarity search in
high-dimensional spaces},
  journal = {IEEE Transactions on Big Data},
  year = {2017},
  pages = {1--13},
}




You are the 505952th visitor

Vincent Gripon's Homepage