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

Yusuke Matsui, Toshihiko Yamasaki, Kiyoharu Aizawa; The IEEE International Conference on Computer Vision (ICCV), 2015, pp. 1940-1948

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.

Related Material


[pdf]
[bibtex]
@InProceedings{Matsui_2015_ICCV,
author = {Matsui, Yusuke and Yamasaki, Toshihiko and Aizawa, Kiyoharu},
title = {PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables},
booktitle = {The IEEE International Conference on Computer Vision (ICCV)},
month = {December},
year = {2015}
}