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

Yusuke Matsui, Toshihiko Yamasaki, Kiyoharu Aizawa

Introduction

In large-scale data retrieval, finding the nearest neighbor to a high-dimensional query vector among billions of items is a significant challenge. Product Quantization (PQ) has emerged as a standard solution, compressing vectors into short codes (e.g., 64 bits) to fit massive datasets into a server's RAM. However, searching these codes typically relies on a linear scan—an $O(N)$ process that becomes prohibitively slow as the database size $N$ reaches the billion-scale.

Existing acceleration techniques, such as inverted indexing, often require extensive manual parameter tuning and dataset-specific training. PQTable addresses these limitations by providing a hash-table-based search method that is both significantly faster than linear scans and more robust than traditional indexing methods.

Methodology

The core innovation of PQTable is treating the PQ code as a key in a hash table. This approach transforms the search from a linear scan into a series of hash lookups. To overcome the challenges of sparse high-dimensional code spaces and potential empty entries, the authors introduced two key mechanisms:

  1. Multisequence Candidate Generation: To handle the "empty-entries problem"—where a query's exact PQ code does not exist in the database—PQTable uses a multisequence algorithm. This algorithm systematically explores the nearest PQ codes in increasing order of distance, ensuring that candidates are always found.
  2. Table Division and Merging: To manage the "long-code problem" (e.g., $2^{64}$ possible values for a 64-bit code), the system splits the long code into multiple smaller tables (e.g., four 16-bit tables). The results from these tables are then merged through a checking process to identify the true nearest neighbors.
Comparison of search architectures: (a) Linear ADC scan, (b) Short-code-based inverted indexing, and (c) the proposed PQTable.

Unlike inverted indexing, PQTable provides a formula to automatically determine the optimal number of table splits based on database size and code length, making it a "plug-and-play" solution.

Experimental Setup

The authors evaluated PQTable primarily on the SIFT1B dataset, which contains one billion 128-dimensional SIFT features. Additional testing on the GIST1M dataset (one million features) confirmed the method's consistency across different data distributions and types.

Key Results and Insights

PQTable achieves massive speedups while maintaining the exactness of a linear PQ scan. Because it is not an approximation of the PQ search but rather a faster implementation, it produces identical results to a full linear scan.

Performance metrics for PQTable: (a) Recall@1 and (b) Runtime per query as a function of database size N.

Key performance highlights include:

  • Speed: On SIFT1B, PQTable was up to 100,000 times faster than a linear scan for 32-bit codes.
  • Latency: For 64-bit codes on a billion items, PQTable reduced search time from 18 seconds (linear scan) to just 10.3 milliseconds.
  • Efficiency: The method leverages a "hot spot" phenomenon where optimal table splitting ensures most queries are resolved within the first few hash lookups.

Conclusion and Future Work

While PQTable offers significant speed and ease of use, it does involve a memory overhead compared to linear scans (e.g., ~20 GB vs 8 GB for a billion 64-bit codes). Furthermore, its efficiency decreases for extremely long codes (exceeding 128 bits). Future research may focus on optimizing memory usage and extending the method's effectiveness to even higher-dimensional code spaces. Nevertheless, for dynamic databases requiring fast, exact, and parameter-free search, PQTable represents a major advancement over current state-of-the-art methods.

Summary updated

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},
}
Figure