AnnArbor: Approximate Nearest Neighbors Using Arborescence Coding

Artem Babenko Yandex, Victor Lempitsky

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    6 Citations (Scopus)

    Abstract

    To compress large datasets of high-dimensional descriptors, modern quantization schemes learn multiple codebooks and then represent individual descriptors as combinations of codewords. Once the codebooks are learned, these schemes encode descriptors independently. In contrast to that, we present a new coding scheme that arranges dataset descriptors into a set of arborescence graphs, and then encodes non-root descriptors by quantizing their displacements with respect to their parent nodes. By optimizing the structure of arborescences, our coding scheme can decrease the quantization error considerably, while incurring only minimal overhead on the memory footprint and the speed of nearest neighbor search in the compressed dataset compared to the independent quantization. The advantage of the proposed scheme is demonstrated in a series of experiments with datasets of SIFT and deep descriptors.

    Original languageEnglish
    Title of host publicationProceedings - 2017 IEEE International Conference on Computer Vision, ICCV 2017
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages4895-4903
    Number of pages9
    ISBN (Electronic)9781538610329
    DOIs
    Publication statusPublished - 22 Dec 2017
    Event16th IEEE International Conference on Computer Vision, ICCV 2017 - Venice, Italy
    Duration: 22 Oct 201729 Oct 2017

    Publication series

    NameProceedings of the IEEE International Conference on Computer Vision
    Volume2017-October
    ISSN (Print)1550-5499

    Conference

    Conference16th IEEE International Conference on Computer Vision, ICCV 2017
    Country/TerritoryItaly
    CityVenice
    Period22/10/1729/10/17

    Fingerprint

    Dive into the research topics of 'AnnArbor: Approximate Nearest Neighbors Using Arborescence Coding'. Together they form a unique fingerprint.

    Cite this