GoKawiilIVF makes search fast by skipping most of the database, but leaves every vector uncompressed. One billion SIFT descriptors still cost 512 GB of RAM. Product Quantization (PQ), introduced by Jégou, Douze and Schmid (2011), is the compression trick FAISS builds on to shrink each vector to 8 bytes while keeping distance estimates meaningful.
Same centroids, a different job
§4 used centroids to partition the search space. PQ uses them to compresseach vector. Same K-Means math, new purpose: the centroid's index becomes the vector. If your codebook has k centroids, any vector collapses to one integer in {0,1,…,k−1}.
A pixel-sized analogy
A 24-bit RGB pixel can be any of 16.7 million colors. A GIF gives up some of that range: it picks a 256-color palette and replaces every pixel with an 8-bit index into it. Storage drops 3×, the picture still looks like the picture. That palette is a codebook; the index is a code.
A 128-D SIFT descriptor is just a very long pixel. We want the same trick: find a palette of representative vectors, replace every descriptor with its nearest palette index.
How many bits does an index cost?
To label k centroids uniquely you need enough bits to distinguish all of them. Each bit doubles the number of labels, so the code length is ⌈log2k⌉ bits. Concretely:
k = 256 centroids → lo g 2 256 = 8 bits per code (1 byte)
centroids → bits per code (1 byte) k = 1 , 024 centroids → lo g 2 1024 = 10 bits
... continue reading