Product split trees

Artem Babenko, Victor Lempitsky

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

    6 Citations (Scopus)

    Abstract

    In this work, we introduce a new kind of spatial partition trees for efficient nearest-neighbor search. Our approach first identifies a set of useful data splitting directions, and then learns a codebook that can be used to encode such directions. We use the product-quantization idea in order to make the effective codebook large, the evaluation of scalar products between the query and the encoded splitting direction very fast, and the encoding itself compact. As a result, the proposed data srtucture (Product Split tree) achieves compact clustering of data points, while keeping the traversal very efficient. In the nearest-neighbor search experiments on high-dimensional data, product split trees achieved state-of-the-art performance, demonstrating better speed-accuracy tradeoff than other spatial partition trees.

    Original languageEnglish
    Title of host publicationProceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages6316-6324
    Number of pages9
    ISBN (Electronic)9781538604571
    DOIs
    Publication statusPublished - 6 Nov 2017
    Event30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017 - Honolulu, United States
    Duration: 21 Jul 201726 Jul 2017

    Publication series

    NameProceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017
    Volume2017-January

    Conference

    Conference30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017
    Country/TerritoryUnited States
    CityHonolulu
    Period21/07/1726/07/17

    Fingerprint

    Dive into the research topics of 'Product split trees'. Together they form a unique fingerprint.

    Cite this