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

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

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.