Computer vision: Memory vectors and group testing for similarity search in high-dimensional spaces
Speaker: Hervé Jégou, INRIA Rennes
In this talk, the speaker will present two strategies to store and search in a set of high-dimensional vectors.
• The first strategy uses an architecture that consists of several memory vectors, each of which summarizes a fraction of the database by a single representative vector. The membership of the query to the memory vector is tested by a simple correlation with its representative vector. This representative optimizes the membership hypothesis test when the query is a simple perturbation of a stored vector. This method is especially effective in high-dimensional spaces.
• The second strategy assumes that only a fraction of the vectors are positives. In this case, we employ a graph-based architecture and employ a simple adaptive group testing algorithm to determine the largest similarities.
Compared to exhaustive search, both approaches finds the most similar database vectors with a lower complexity without a noticeable reduction in search quality.
This is joint work with Teddy Furon, Vincent Gripon, Ahmet Iscen, Michael Rabbat and Miaojing Shi.
More information on XRCE seminars.