The Inverted Multi-Index

Add to your list(s) Download to your calendar using vCal

• Victor Lempitsky, Yandex
• Thursday 07 June 2012, 14:00-15:00
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

I will present a new data structure for efficient similarity search in very large datasets of high-dimensional vectors. This structure called the inverted multi-index generalizes the inverted index idea by replacing the standard quantization within inverted indices with product quantization. For very similar retrieval complexity and pre-processing time, inverted multi-indices achieve a much denser subdivision of the search space compared to inverted indices, while retaining their memory efficiency. Our experiments with large datasets of SIFT and GIST vectors demonstrate that because of the denser subdivision, inverted multi-indices are able to return much shorter candidate lists with higher recall. Augmented with a suitable reranking procedure, multi-indices were able to improve the speed of approximate nearest neighbor search on the dataset of 1 billion SIFT vectors by an order of magnitude compared to the best previously published systems, while achieving better recall and incurring only few percent of memory overhead. This is a joint work with Artem Babenko.

This talk is part of the Microsoft Research Machine Learning and Perception Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge University Engineering Department Talks
• Centre for Smart Infrastructure & Construction
• Featured lists
• Machine Learning Summary
• Methodology in design research
• Microsoft Research Cambridge, public talks
• Microsoft Research Machine Learning and Perception Seminars
• School of Technology
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• de239's list
• engineering

Note that ex-directory lists are not shown.