Pqtable: Non-exhaustive Fast Search For Product-quantized Codes Using Hash Tables

Abstract

In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by using its PQ-code as a key. For querying, an input vector is PQ-encoded and hashed, and the items associated with that code are then retrieved. The proposed PQTable produces the same results as a linear PQ scan, and is 10^2 to 10^5 times faster. Although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods require manually-designed parameter setting and significant training; our PQTable is free of these limitations, and therefore offers a practical and effective solution for real-world problems. Specifically, when the vectors are highly compressed, our PQTable achieves one of the fastest search performances on a single CPU to date with significantly efficient memory usage (0.059 ms per query over 10^9 data points with ju

Stats

• citations8
• S2 citations—
• github stars0
• HF likes0
• heat score7.16
• arxiv keymatsui2017pqtable

Related papers

• End-to-end Supervised Product Quantization For Image Search And Retrieval (2017)13.05
• Jointly Optimizing Query Encoder And Product Quantization To Improve Retrieval Performance (2021)12.74
• Online Product Quantization (2017)10.61
• Matching-oriented Product Quantization For Ad-hoc Retrieval (2021)2.29
• Beyond Product Quantization: Deep Progressive Quantization For Image Retrieval (2019)12.95
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Polysemous Codes (2016)11.49
• Quicker ADC : Unlocking The Hidden Potential Of Product Quantization With SIMD (2018)10.50