References

1. Hervé Jégou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE TPAMI, 2011. Introduces PQ, ADC, and the IVFADC system this book reproduces.

2. Tiezheng Ge, Kaiming He, Qifa Ke, Jian Sun. Optimized Product Quantization. CVPR 2013. OPQ: a learned rotation before PQ that improves recall (OPQ in FAISS).

3. Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Information Theory, 1982 (work from 1957). The k-means algorithm at the core of every codebook here.

4. Jeff Johnson, Matthijs Douze, Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Big Data, 2019. The FAISS library and its GPU implementations.

5. Ruiqi Guo et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ScaNN). ICML 2020. Quantization tuned for maximum inner-product search.

Tools & systems

• FAISS: IndexFlat, IndexIVFFlat, IndexPQ, IndexIVFPQ, IndexScalarQuantizer, IndexHNSWFlat, and the index factory.
• ScaNN (Google), anisotropic quantization for MIPS.
• Vector databases: Qdrant, Weaviate, Milvus, Pinecone (IVF/PQ/HNSW indexes).

Related books here

• HNSW from Scratch, the graph-navigation side of vector search.
• KTS from Scratch, kernel temporal segmentation.

This book's code

• code/ivfpq.py, k-means, IVF, PQ, IVFPQ.
• code/demo.py, recall vs. memory vs. work comparison.
• code/pqtool.py, the trade-off estimator CLI.

All depend only on NumPy and the standard library.