PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables

Yusuke Matsui, Toshihiko Yamasaki, Kiyoharu Aizawa

Abstract

We propose the product quantization table (PQTable), a product quantization-based hash table that is fast and requires neither parameter tuning nor training steps. The PQTable produces exactly the same results as a linear PQ search, and is 102 to 105 times faster when tested on the SIFT1B data. In addition, although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods do require manually designed parameter setting and much training, whereas our method is free from them. Therefore, PQTable offers a practical and useful solution for real-world problems.
BibTeX
@inproceedings{matsui2015pqtable,
  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/CVF International Conference on Computer Vision},
  year = {2015},
  doi = {10.1109/iccv.2015.225},
}

Loading related content...

Figure