Product Quantization (PQ) — how does it compress vectors?
hardAnswer
- Split d-dim vector into m sub-vectors of d/m dims.
- Cluster each sub-vector space separately (k centroids per subspace, k typically 256).
- Encode a vector as m codes .
- Distance computed via precomputed lookup tables between query and centroids → very fast. 8-32× compression vs float32 with modest recall loss.
- Foundation of FAISS's scale to billions of vectors.
Check yourself — multiple choice
- Random
- Split vector into m sub-vectors, k-means each subspace, encode as m codes; distance via LUT; 8-32× compression; core of FAISS at billion-scale
- Same as HNSW
- Not real
PQ: sub-vector quantization + LUT distance; 8-32× compression.
#applications#similarity
Practise Unsupervised Learning
214 interview questions in this topic.
Related questions
- HNSW — how does it work?
- Locality-Sensitive Hashing (LSH) — the core trick.
- MinHash — how does it estimate Jaccard similarity?
- Interview: your image dataset (10M) has near-duplicates — how do you dedup at scale?
- How do you cluster mixed numeric + categorical data?
- Why do you scale features before k-means?