5 ms·

Product quantization for vector search

51 points by fzliu 3y ago

fzliu 3y ago
For folks interested in the rest of our vector search 101 series, here's a link: https://zilliz.com/blog?tag=39&page=1 https://zilliz.com/blog?tag=39&page=1
pbadams 3y ago
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 https://www.jstage.jst.go.jp/article/mta/6/1/6_2/_pdf (2018)
- fzliu 3y ago
  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.
  - jhj 3y ago
    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).
jeffchuber 3y ago
Be careful with PQ, streaming updates will degrade recall performance a lot (and in ways you may miss)
- fzliu 3y ago
  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 https://milvus.io/docs/glossary.md#Segment
jadbox 3y ago
Is there a product qantasization indexer plugin for postgres?
- fzliu 3y ago
  AFAIK pgvector only supports IVF, no PQ (nor HNSW).

51 points by fzliu 3y ago

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

pbadams 3y ago

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 https://www.jstage.jst.go.jp/article/mta/6/1/6_2/_pdf (2018)

fzliu 3y ago
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.
- jhj 3y ago
  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).

jeffchuber 3y ago

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

fzliu 3y ago
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 https://milvus.io/docs/glossary.md#Segment

jadbox 3y ago

Is there a product qantasization indexer plugin for postgres?

fzliu 3y ago
AFAIK pgvector only supports IVF, no PQ (nor HNSW).