Online Product Quantization
2017 · Donna Xu, Ivor W. Tsang, Ying Zhang
Abstract
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 beh
Authors
(none)
Tags
Stats
Related papers
- Matching-oriented Product Quantization For Ad-hoc Retrieval (2021)2.29
- Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00
- Routing-guided Learned Product Quantization For Graph-based Approximate Nearest Neighbor Search (2023)4.52
- Rabitq: Quantizing High-dimensional Vectors With A Theoretical Error Bound For Approximate Nearest Neighbor Search (2024)12.54
- End-to-end Supervised Product Quantization For Image Search And Retrieval (2017)13.05
- Pqtable: Non-exhaustive Fast Search For Product-quantized Codes Using Hash Tables (2017)7.16
- Beyond Product Quantization: Deep Progressive Quantization For Image Retrieval (2019)12.95
- Jointly Optimizing Query Encoder And Product Quantization To Improve Retrieval Performance (2021)12.74