5 ms·

Nice this will get you acquainted with many of the methods used currently, as my small addition to the list of things you can learn. https://ai.googleblog.com/2

Nice this will get you acquainted with many of the methods used currently, as my small addition to the list of things you can learn. https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html https://ai.googleblog.com/2020/07/announcing-scann-efficient... https://github.com/google-research/google-research/tree/master/scann https://github.com/google-research/google-research/tree/mast... Google released SCaNN a few years ago and back then it wasn't implemented in many tools like Milvus etc. Maybe it is now, it's been a few years since I needed a scalable vector db. I believe it's still state of the art, and they use a novel approach to quantization, which was the key intuition. I didn't see it included in the PDF from a quick scan (hah!)

bravura 3y ago
I remember SCaNN. Are there easy to use implementations available now? You also seem unsure. Personally, I love a cheat-sheet like in Slide 7 of the presentation. It's a game-tree for what ANN implementation to use, given your problem setting and the assumption you don't want to do groundbreaking ANN research; rather, you have an ANN problem you need to solve on the path to your actual problem. Maybe that's why SCaNN wasn't cited? A quick google reveals that SCaNN is available on pypi from Google: https://pypi.org/project/scann/ https://pypi.org/project/scann/ Do any users have any feedback or experiences to share? [edit: GPT4, comparing hnwslib and SCaNN: "Note that SCaNN recently ceased to be supported by Google Research, and there won't be any further improvements, bug fixes, or documentation updates from them. However, you can still use and get support from the community. This recent change in support could shift preference towards hnswlib for future applications."]
- ianbutler 3y ago
  GPT4 is only trained on data up to 2021, and the library has commits as recent as two months ago. So I think that may be a hallucination. A quick google also reveals nothing like that. It's been a while but I also remember HSNW having undesirable characteristics for large scale vector search (compared to other methods), so I'm not sure there. I did do a quick search and saw there are methods that make it more suitable, but again it's been 3 years now since I've used anything in this area. Edit: I got curious, https://ann-benchmarks.com/ https://ann-benchmarks.com/ So I was mis remembering a bit, HSNW is pretty good overall depending on your implementation!
- jhj 3y ago
  SCaNN (the paper) is roughly two different things: 1. a SIMD-optimized form of product quantization (PQ), where code to distance lookup can be performed in SIMD registers 2. anisotropic quantization to bias the database towards returning better maximum inner product search (MIPS) candidates, versus usual quantization (such as PQ) that aims to minimize compressed vector reconstruction error. In MIPS it is much more likely that the query data set may be of a completely different distribution than the database vectors. If your application needs L2 lookup rather than MIPS which does not admit a metric, then only the PQ part is relevant. For cosine similarity, you can get that by normalizing all vectors to the surface of a hypersphere, in which case it has the same order as L2 (see "L2 normalized Euclidean distance" on https://en.wikipedia.org/wiki/Cosine_similarity https://en.wikipedia.org/wiki/Cosine_similarity ). SCaNN is implemented in Faiss CPU, on the GPU the fast PQ part is less relevant due to the greater register set size and throughput (rather than latency) optimized nature of the hardware, but the GPU version is more geared towards batch lookup in any case. https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-(FastScan) https://github.com/facebookresearch/faiss/wiki/Fast-accumula... https://github.com/facebookresearch/faiss/wiki/Indexing-1M-vectors#4-bit-pq-comparison-with-scann https://github.com/facebookresearch/faiss/wiki/Indexing-1M-v... We have not found the anisotropic quantization part to be that useful for large datasets, but results may vary. Graph-based ANN techniques tend to be better in many cases for these small datasets than IVF based strategies. (I'm the author of GPU Faiss)
  - chuckcode 3y ago
    Thanks for details! Few follow up questions: - I've seen neural nets using int8 for matrix multiplication to reduce memory size [1]. Do you think something similar could be useful in the ANN space? - Do you know of any studies using Faiss looking at speed/cost tradeoffs of RAM vs flash vs Disk for storage? - Are there recommended ways to update Faiss index with streaming data, e.g. updating the vectors continuously? Seems like more and more use cases for Faiss as neural nets become more and more core to workflows. Would like to try and figure out the configurations that are optimized to minimize carbon usage in addition to latency and recall metrics. [1] https://arxiv.org/abs/2208.07339 https://arxiv.org/abs/2208.07339 (edit for formatting)
- sgt101 3y ago
  > I remember SCaNN. Are there easy to use implementations available now? Yes, on gcp in vertex AI. GPT4 is talking utter horseshit. https://cloud.google.com/vertex-ai/docs/matching-engine/ann-service-overview https://cloud.google.com/vertex-ai/docs/matching-engine/ann-...
eternalban 3y ago
both are 2020.
fzliu 3y ago
SCaNN is coming to Milvus very soon (we've seen some demand from the community). Stay tuned.

bravura 3y ago

I remember SCaNN. Are there easy to use implementations available now? You also seem unsure. Personally, I love a cheat-sheet like in Slide 7 of the presentation. It's a game-tree for what ANN implementation to use, given your problem setting and the assumption you don't want to do groundbreaking ANN research; rather, you have an ANN problem you need to solve on the path to your actual problem. Maybe that's why SCaNN wasn't cited? A quick google reveals that SCaNN is available on pypi from Google: https://pypi.org/project/scann/ https://pypi.org/project/scann/ Do any users have any feedback or experiences to share? [edit: GPT4, comparing hnwslib and SCaNN: "Note that SCaNN recently ceased to be supported by Google Research, and there won't be any further improvements, bug fixes, or documentation updates from them. However, you can still use and get support from the community. This recent change in support could shift preference towards hnswlib for future applications."]

ianbutler 3y ago
GPT4 is only trained on data up to 2021, and the library has commits as recent as two months ago. So I think that may be a hallucination. A quick google also reveals nothing like that. It's been a while but I also remember HSNW having undesirable characteristics for large scale vector search (compared to other methods), so I'm not sure there. I did do a quick search and saw there are methods that make it more suitable, but again it's been 3 years now since I've used anything in this area. Edit: I got curious, https://ann-benchmarks.com/ https://ann-benchmarks.com/ So I was mis remembering a bit, HSNW is pretty good overall depending on your implementation!
jhj 3y ago
SCaNN (the paper) is roughly two different things: 1. a SIMD-optimized form of product quantization (PQ), where code to distance lookup can be performed in SIMD registers 2. anisotropic quantization to bias the database towards returning better maximum inner product search (MIPS) candidates, versus usual quantization (such as PQ) that aims to minimize compressed vector reconstruction error. In MIPS it is much more likely that the query data set may be of a completely different distribution than the database vectors. If your application needs L2 lookup rather than MIPS which does not admit a metric, then only the PQ part is relevant. For cosine similarity, you can get that by normalizing all vectors to the surface of a hypersphere, in which case it has the same order as L2 (see "L2 normalized Euclidean distance" on https://en.wikipedia.org/wiki/Cosine_similarity https://en.wikipedia.org/wiki/Cosine_similarity ). SCaNN is implemented in Faiss CPU, on the GPU the fast PQ part is less relevant due to the greater register set size and throughput (rather than latency) optimized nature of the hardware, but the GPU version is more geared towards batch lookup in any case. https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-(FastScan) https://github.com/facebookresearch/faiss/wiki/Fast-accumula... https://github.com/facebookresearch/faiss/wiki/Indexing-1M-vectors#4-bit-pq-comparison-with-scann https://github.com/facebookresearch/faiss/wiki/Indexing-1M-v... We have not found the anisotropic quantization part to be that useful for large datasets, but results may vary. Graph-based ANN techniques tend to be better in many cases for these small datasets than IVF based strategies. (I'm the author of GPU Faiss)
- chuckcode 3y ago
  Thanks for details! Few follow up questions: - I've seen neural nets using int8 for matrix multiplication to reduce memory size [1]. Do you think something similar could be useful in the ANN space? - Do you know of any studies using Faiss looking at speed/cost tradeoffs of RAM vs flash vs Disk for storage? - Are there recommended ways to update Faiss index with streaming data, e.g. updating the vectors continuously? Seems like more and more use cases for Faiss as neural nets become more and more core to workflows. Would like to try and figure out the configurations that are optimized to minimize carbon usage in addition to latency and recall metrics. [1] https://arxiv.org/abs/2208.07339 https://arxiv.org/abs/2208.07339 (edit for formatting)
sgt101 3y ago
> I remember SCaNN. Are there easy to use implementations available now? Yes, on gcp in vertex AI. GPT4 is talking utter horseshit. https://cloud.google.com/vertex-ai/docs/matching-engine/ann-service-overview https://cloud.google.com/vertex-ai/docs/matching-engine/ann-...

eternalban 3y ago

both are 2020.

fzliu 3y ago

SCaNN is coming to Milvus very soon (we've seen some demand from the community). Stay tuned.