# Online Product Quantization

arXiv: https://arxiv.org/abs/1711.10775 · HTML: https://mlsanity.com/paper/1711.10775/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2017.

## Built on by (most cited first, 11 of 11)

- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Embedding in Recommender Systems: A Survey](https://mlsanity.com/paper/2310.18608/) (2023)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Discrete Tokenization for Multimodal LLMs: A Comprehensive Survey](https://mlsanity.com/paper/2507.22920/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [Driving-RAG: Driving Scenarios Embedding, Search, and RAG Applications](https://mlsanity.com/paper/2504.04419/) (2025)
- [Clustering the Sketch: A Novel Approach to Embedding Table Compression](https://mlsanity.com/paper/2210.05974/) (2022)
- [AQPIM: Breaking the PIM Capacity Wall for LLMs with In-Memory Activation Quantization](https://mlsanity.com/paper/2604.18137/) (2026)
- [QET: Enhancing Quantized LLM Parameters and KV cache Compression through Element Substitution and Residual Clustering](https://mlsanity.com/paper/2407.03637/) (2024)

## Abstract (arXiv)

Approximate nearest neighbor (ANN) search has achieved great success in many tasks. However, existing popular methods for ANN search, such as hashing and quantization methods, are designed for static databases only. They cannot handle well the database with data distribution evolving dynamically, due to the high computational effort for retraining the model based on the new database. In this paper, we address the problem by developing an online product quantization (online PQ) model and incrementally updating the quantization codebook that accommodates to the incoming streaming data. Moreover, to further alleviate the issue of large scale computation for the online PQ update, we design two budget constraints for the model to update partial PQ codebook instead of all. We derive a loss bound which guarantees the performance of our online PQ model. Furthermore, we develop an online PQ model over a sliding window with both data insertion and deletion supported, to reflect the real-time behaviour of the data. The experiments demonstrate that our online PQ model is both time-efficient and effective for ANN search in dynamic large scale databases compared with baseline methods and the idea of partial PQ codebook update further reduces the update cost.