Product Quantizers for k-NN Tutorial Part 1

submited by
Style Pass
2021-06-28 15:30:08

A product quantizer is a type of “vector quantizer” (I’ll explain what that means later on!) which can be used to accelerate approximate nearest neighbor search. They’re of particular interest because they are a key element of the popular Facebook AI Similarity Search (FAISS) library released in March 2017. In part 1 of this tutorial, I’ll be providing an explanation of a product quantizer in its most basic form, as used for implementing approximate nearest neighbors search (ANN). Then in part 2 I explain the “IndexIVFPQ” index from FAISS, which adds a couple more features on top of the basic product quantizer.

Unlike tree-based indexes used for ANN, a k-NN search with a product quantizer alone still performs an “exhaustive search”, meaning that a product quantizer still requires comparing the query vector to every vector in the database. The key is that it approximates and greatly simplifies the distance calculations.

(Note that the IndexIVFPQ index in FAISS does perform pre-filtering of the dataset before using the product quantizer–I cover this in part 2).

Leave a Comment