product quantization instrument
| Definition | Splitting a vector into pieces and quantizing each piece with its own codebook. Chapter 11. Also product quantiz, codebook. |
|---|---|
| Example | A 768-dimensional vector split into 8 pieces of 96, each coded with 256 centroids, costs 8 bytes. |
| Book | Data Mining as Observation, draft 0.2, commit f3914f0; entry id product-quantization, kind instrument. |
| Status | no ledger row names this entry. Corrections: none recorded. |
| Defining equation | none |
| Assumptions and scope |
|
| Prior art | none recorded |
| Evidence | lean/DataMiningAsObservation/ProductQuantization.lean |
| Reviewed | not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page. |
Equation
none
Conditions
- Splitting a vector into pieces and quantizing each with its own codebook. The squared error of the whole is the sum of the pieces’ errors, so the best code for the whole is the best code for each piece separately, and K entries per piece over M pieces address K to the M cells in M log₂ K bits.
- It is evaluated by recall at k per stratum and by the rank certificate, never by reconstruction error, and the anti-hub stratum is where it fails first.
Conditions are curated in entries.toml rather than read
from a record.
Ledger
none
First stated
Jégou, Douze, and Schmid, product quantization for nearest neighbor search, 2011, as chapter 11 section 11.3 of Data Mining as Observation presents it, with the program’s comparisons in openvector-bench and turboquant-pro.
Measurements
none
Failures and corrections
none
Invariance envelope
none declared
Machine checked
lean/DataMiningAsObservation/ProductQuantization.lean,
theorems sq_error_add, inf_add,
bits_of_codebooks, table_row, at
observation-data-mining f3914f0; what the check covers is stated in the
book’s appendix
C.
Used in
Data Mining as Observation chapters 0, 4, 8, 11, 13.
Related
recall at k; anti-hub; water-filling; rank certificate.
See also
Book equations stated beside the entry’s terms, not defining it: 11.3, 4.2.
Ledger rows that cite the entry’s records without naming it: NEG-14.
Sources-table rows that share a record with the entry without naming it: chapter 10 section 10.4.
Status
Generated 2026-09-10 by encyclopedia/generate.py; book
at observation-data-mining f3914f0; the commit of every record is listed
in the encyclopedia’s provenance.