The inverted multi-index

Artem Babenko, Victor Lempitsky

    Research output: Contribution to journalArticlepeer-review

    98 Citations (Scopus)

    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.

    Original languageEnglish
    Article number6915715
    Pages (from-to)1247-1260
    Number of pages14
    JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
    Volume37
    Issue number6
    DOIs
    Publication statusPublished - 1 Jun 2015

    Keywords

    • Image retrieval
    • Index
    • nearest neighbor search
    • product quantization

    Fingerprint

    Dive into the research topics of 'The inverted multi-index'. Together they form a unique fingerprint.

    Cite this