The Inverted Multi-Index ← Department of Cybernetics

Denis Efremov presents The Inverted Multi-Index

On 2019-09-12 11:00:00 at G205, Karlovo náměstí 13, Praha 2
Reading group on the work "The Inverted Multi-Index" (PAMI 2014) by A. Babenko
and V. Lempitsky presented by Denis Efremov.

Paper abstract: A new data structure for efficient similarity search in very
large datasets of high-dimensional vectors is introduced. 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 significantly improve the speed of
approximate nearest neighbor search on the dataset of 1 billion SIFT vectors
compared to the best previously published systems, while achieving better
recall and incurring only few percent of memory overhead.

Paper URL:
http://cmp.felk.cvut.cz/~toliageo/rg/papers/BabenkoLempitsky_PAMI2014_The%20Inverted%20Multi-Index.pdf

Instructions for participants: The reading group studies the literature in the
field of pattern recognition and computer vision. At each meeting one or more
papers are prepared for presentation by a single person, the presenter. The
meetings are open to anyone, regarding their background. It is assumed that
everyone attending the reading group has, at least briefly, read the paper –
not necessarily understanding everything. Attendants should preferably send
questions about the unclear parts to the speaker at least one day in advance.
During the presentation we aim to have a fruitful discussion, a critical
analysis of the paper, as well as brainstorming for creative extensions.

See the page of reading groups
http://cmp.felk.cvut.cz/~toliageo/rg/index.html
Responsible person: Petr Pošík