Product quantization for vector search | Hacker News Reader

Product quantization for vector search

zilliz.com

51 pointsfzliu8 comments

There are a lot of directions people try to go, making different tradeoffs in the complexity of the clustering, the loss from the quantization, the impact on performance (esp. trying to get some subset of the tables to fit in cache). Readers might be interested in [1], which gives a survey of some of the directions.

In general though PQ is a pretty good baseline. I'm glad all these vector DB companies seem to have decided that the best form of marketing is high-quality summaries/tutorials about fundamental concepts, it's a good contribution to the community.

[1] Fig. 1 in https://www.jstage.jst.go.jp/article/mta/6/1/6_2/_pdf (2018)

Just read the abstract and intro for the link you posted - thanks for sharing.

As great as HNSW and other graph-based indexes are, I think PQ and other encoder/decoder-based methods are still incredibly important for ANN search in general. In particular, it should be possible to learn some sort of joint encoding with neural networks targeted towards different modalities.

PQ is just a vector compression/quantization method, not an approximate k-NN search algorithm (like cell-probe or bucketing based methods such as IVF or LSH, or graph-based methods such as HNSW). HNSW can be used together with PQ encoding, for instance.

However PQ does have the nice property that distance computation can be performed with lookup-adds instead of multiply-adds but in practice performance is lower than normal brute-force multiply-add inner product because lookup table gather is slow on CPU or GPU relative to arithmetic. The gain of PQ is by dimensionality reduction (a 128 dimensional vector can be compressed as 8 PQ codes resulting in 8 lookup-adds, versus 128 FMAs for the brute-force inner product, say).

For folks interested in the rest of our vector search 101 series, here's a link: https://zilliz.com/blog?tag=39&page=1

Be careful with PQ, streaming updates will degrade recall performance a lot (and in ways you may miss)

A naive PQ index that trains the quantizer once and reuses the same codebook for recent data definitely has this problem. We (Milvus/Zilliz) break up all the vectors into multiple indexes at certain checkpoints which we call segments. This doesn't fully solve the problem of degraded performance with PQ or hybrid PQ indexes, but certainly helps mitigate it.

More info here: https://milvus.io/docs/glossary.md#Segment

Is there a product qantasization indexer plugin for postgres?

AFAIK pgvector only supports IVF, no PQ (nor HNSW).

Reply on news.ycombinator.com