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

Yusuke Matsui; Toshihiko Yamasaki; Kiyoharu Aizawa

ICCV 2015poster44 citations

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 10^2 to 10^5 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{iccv2015_pqtablefastexact,
  title = {PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables},
  author = {Yusuke Matsui and Toshihiko Yamasaki and Kiyoharu Aizawa},
  booktitle = {ICCV 2015},
  year = {2015}
}