Quantization

In a vector retrieval system, it is usually not enough to process queries as fast as possible. It is equally as important to reduce the size of the index by compressing vectors. Compression, however, must be done in such a way that either decompressing the vectors during retrieval incurs a negligible cost, or distances can be computed (approximately) in the compressed domain, rendering it unnecessary to decompress compressed vectors during retrieval. This chapter introduces a class of vector compression algorithms, known as quantization, that is inspired by clustering.