IEEE International Conference on Computer Vision (ICCV) 2015, TMM 2018

PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables

Toshihiko Yamasaki
The University of Tokyo

Kiyoharu Aizawa
The University of Tokyo


A datas tructure of PQTable.

Runtime per query (SIFT1B).

Abstract

In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by using its PQ-code as a key. For querying, an input vector is PQ-encoded and hashed, and the items associated with that code are then retrieved. The proposed PQTable produces the same results as a linear PQ scan, and is 10^2 to 10^5 times faster. Although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods require manually-designed parameter setting and significant training; our PQTable is free of these limitations, and therefore offers a practical and effective solution for real-world problems. Specifically, when the vectors are highly compressed, our PQTable achieves one of the fastest search performances on a single CPU to date with significantly efficient memory usage (0.059 ms per query over 10^9 data points with just 5.5 GB memory consumption). Finally, we show that our proposed PQTable can naturally handle the codes of an optimized product quantization (OPQTable).

Video

Links

Publication

  • Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa.
    PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables.
    IEEE Transactions on Multimedia 2018. (extended version of ICCV paper)
    [IEEE] [arXiv] [Code]
  • Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa.
    PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization using Hash Tables.
    Proceedings of 15th IEEE International Conference on Computer Vision (ICCV) 2015.
    [Paper (author version)] [Supplementary] [IEEE] [CVF]

BibTeX

@article{tmm_matsui_2018,
    author={Yusuke Matsui and Toshihiko Yamasaki and Kiyoharu Aizawa},
    title={PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables},
    journal={IEEE Transactions on Multimedia},
    volume={PP},
    number={99},
    pages={1-1},
    year={2018}
}

@inproceedings{iccv_matsui_2015,
    author={Yusuke Matsui and Toshihiko Yamasaki and Kiyoharu Aizawa},
    title={PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables},
    booktitle={IEEE International Conference on Computer Vision (ICCV)},
    pages={1940-1948},
    year={2015}
}