7 ms·

Approximate Nearest Neighbor Oh Yeah (Annoy)

146 points by fzliu 3y ago

PaulHoule 3y ago
Funny I got interested in nearest-neighbor search for this kind of vectors in the early 2000s and there were a lot of papers on the subject that were depressing (had to make a tradeoff that wasn't really attractive) compared to the literature on low-dimensional indexes. Back then I had 250,000 or so vectors and a full scan wasn't that bad. In the 2010s I worked on a dense vector search engine for patents and we had maybe 10 million vectors and still used a scan, I mean, you couldn't ask for a more memory hierarchy and SIMD friendly algorithm. Today I am looking at 1M (larger) vectors and the full scan is still possible but I am using FAISS because it is a bird in the hand and I decided I can live with the tradeoff.
- kristjansson 3y ago
  I mean FAISS has IndexFlatL2 if you have it in hand and _want_ the full scan.
smokracek 3y ago
Does anyone have any recommendations for a decent crash course on using vector DBs in conjuction with LLMs? I wanna do some experimentation with getting a model to comment on the similarity of data vectors etc. and I don't really know where to start.
- minimaxir 3y ago
  If you want to experiment with vector stores, you can do that locally with something like faiss which has good multiplatform support and sufficient tutorials: https://github.com/facebookresearch/faiss https://github.com/facebookresearch/faiss Doing full retrieval-augmented generation (RAG) and getting LLMs to interpret the results has more steps but you get a lot of flexibility, and despite what AI influencers say there's no standard best-practice. When you query a vector DB you get the most similar texts back (or an index integer in the case of faiss), you then feed those result to an LLM like a normal prompt, which can be optimized with prompt engineering. The codifer for the RAG workflow is LangChain, but their demo is substantially more complex and harder-to-use than even a homegrown implementation: https://minimaxir.com/2023/07/langchain-problem/ https://minimaxir.com/2023/07/langchain-problem/
  - marcyb5st 3y ago
    Also, if what you look up has no semantic meaning like parts number you might be better off with an inverted index in addition to ANN lookups. Especially if the embedding model has been trained on a dataset that is not similar to what you use it for. That's a common situation right now with embedding models based on LLMs.
- pokpokpok 3y ago
  I recommend pgvector, it's simple and well featured with good example code. Once you have a dataset of vectors loaded in, the next step is called rag / retrieval augmented generation
- deleted 3y ago
  [deleted]
- malaya_zemlya 3y ago
  deeplearning.ai has a short coursee on the topic https://www.deeplearning.ai/short-courses/large-language-models-semantic-search/ https://www.deeplearning.ai/short-courses/large-language-mod...
- alumic 3y ago
  You might also check out this previous thread on the subject. It offers some pretty fascinating discussions: https://news.ycombinator.com/item?id=35826929 https://news.ycombinator.com/item?id=35826929
- bobvanluijt 3y ago
  (I’m affiliated with Weaviate) You might want to check out this getting started guide. It takes a couple of minutes, and you're good to go https://weaviate.io/developers/weaviate/quickstart https://weaviate.io/developers/weaviate/quickstart
dmezzetti 3y ago
If you want an easy way to evaluate Faiss, Hnswlib and Annoy vector backends, check out txtai - https://github.com/neuml/txtai https://github.com/neuml/txtai. txtai also supports NumPy and PyTorch vector storage. Disclaimer: I am the author of txtai
- Scene_Cast2 3y ago
  Would you have any quick links or data on how they compare in terms of speed and recall?
  - dmezzetti 3y ago
    https://ann-benchmarks.com/ https://ann-benchmarks.com/ is a good resource covering those libraries and much more.
daturkel 3y ago
Annoy came out of Spotify, and they just announced their successor library Voyager [1] last week [2]. [1]: https://github.com/spotify/voyager https://github.com/spotify/voyager [2]: https://engineering.atspotify.com/2023/10/introducing-voyager-spotifys-new-nearest-neighbor-search-library/ https://engineering.atspotify.com/2023/10/introducing-voyage...
- gregsadetsky 3y ago
  Amazing, thanks for the reference! The biggest immediate useful difference that I see is that Annoy uses read-only index files (from the docs: "you can not add more items once the tree has been created" [0]), while Voyager allows you to call `.add_item` at any time (I just pip installed to double check and yes -- it's great). [0] https://github.com/spotify/annoy#summary-of-features https://github.com/spotify/annoy#summary-of-features
  - PLenz 3y ago
    The great thing about Annoy is that you can write the index to disk and thus do big data work on tiny workers at the edge. I've never really seen anything else do the same.
    - gregsadetsky 3y ago
      Oh yeah, Annoy is definitely mmap'ed i.e. you can use the index without loading the index file into memory. And that's very useful. As far as I can see, Voyager requires you to load the index into memory and doesn't (yet?) do mmap. Which... would make sense since you can change the data after loading the index. So, Voyager index files are fully loaded in memory..? Do I have this right?
danbruc 3y ago
That sound pretty much like binary space partitioning [1] which is probably best known for being used in Doom to accelerate the rendering. Also, if you only search the leaf subspace that you query point lies in, then you can in principle be arbitrarily far off from the true nearest neighbor. [1] https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning
- taneq 3y ago
  Yeah, it looks pretty similar to me too. I haven’t read up on vector DBs but I wonder of k-d trees would be a better fit?
- jhj 3y ago
  k-D trees and BSPs don't work well in high dimensions (say >20 to 30 dims), since your true nearest neighbor is highly likely to lie on either side of any dividing hyperplane. If each dividing hyperplane separates a set of vectors into two roughly equal parts, then for N vectors you have something on the order of log2(N) separating planes in order to get down to a single vector per terminal node. But for, say, a billion vectors in a 100-dimensional space (and assuming something like a k-D tree where you partition each dimension at each level), you have only partitioned log2(10^9) ~= 30 dimensions this way, yet there are 70 other dimensions remaining through which you can travel to find your true nearest neighbor (the curse of dimensionality; in high dimensions everything is "near" everything else) that you have not checked if you are discarding subspaces along the way. This is a problem for other approximate methods as well though. IVF methods still do a form of partitioning (via Voronoi cells) but this is obtained by clustering the data so it is more attuned to the global structure of the data rather than greedy divide and conquer. But in IVF methods it is still possible that you need to check every IVF cell in order to find your true nearest neighbor, just that it is less likely to happen in practice because the partitioning is more attuned to the overall structure of data rather than via greedy subdivision.
  - esafak 3y ago
    And LSH uses random hyperplanes.
naillo 3y ago
This is so overcomplicated. You don't need an actual tree that's just a mental model. All you need to do is generate N random hyperplanes (defined via it's normal i.e. generate N normalized vectors in the dimension of your choosing). Then you generate a hash via these by going normal by normal and checking if your query vector `q` is on the left or right side of the normal by checking the sign of the dot product. I.e. `hash = [sign(dot(q, n1)), sign(dot(q, n2)), ...]`. So given a query you find that hash and you get all the vectors with the same hash (using your favorite hash to array data structure, i.e. a dict) and you can further refine the search within that bucket. It's like 10 rows of code.
- rozim 3y ago
  Sounds like you're describing LSH (locality sensitive hashing).
- bigbillheck 3y ago
  > All you need to do It seems to me that your approach is making some assumptions about how the data is distributed that aren't necessarily guaranteed to hold in practice, and a tree has a chance of being robust to at least some of those. For example, whatever random hyperplane you choose has to be informed by your data. Suppose you make a particularly bad choice for one of those hyperplanes, with your approach you'll be stuck with that for all time and have a bit in your hash that's biased to heck, but in the tree approach you only suffer when you hash your way down to the lousy node, and all other paths will be unaffected.
- erikbern 3y ago
  Annoy author here. What you're describing is Locality Sensitive Hashing (LSH) which is something I spent a lot of time trying back in 2009-2012 but never got it working. It has some elegant theoretical properties, but empirically it always has terrible performance. The reason I don't think it works well is that data often lies near a lower-dimensionality manifold that may have some sort of shape. LSH would "waste" most splits (because it doesn't understand the data distribution) but using trees (and finding splits such that the point set is partitioned well) ends up "discovering" the data distribution better. (but HNSW is generally much better than this tree paritioning scheme)
superdug 3y ago
I was so saddened by this title.. I thought there was a way to find annoying neighbors (at homes I’m interested in acquiring) and assumed this was a service for literally finding nearby annoy[ing] neighbors. To then go through the comments and find that this is a service with a minimum input of addresses and census data which are both freely available as is this service. Bravo hn!
debo_ 3y ago
When I saw the "oh yeah" I assumed this was going to be a deepfake Macho Man Randy Savage explaining ANN. I am disappointed.
lootsauce 3y ago
This popped up in the new feed yesterday and seems significant in the ANN space https://news.ycombinator.com/item?id=38054537 https://news.ycombinator.com/item?id=38054537
- lootsauce 3y ago
  Found code for it https://github.com/microsoft/DiskANN https://github.com/microsoft/DiskANN

146 points by fzliu 3y ago

Funny I got interested in nearest-neighbor search for this kind of vectors in the early 2000s and there were a lot of papers on the subject that were depressing (had to make a tradeoff that wasn't really attractive) compared to the literature on low-dimensional indexes. Back then I had 250,000 or so vectors and a full scan wasn't that bad. In the 2010s I worked on a dense vector search engine for patents and we had maybe 10 million vectors and still used a scan, I mean, you couldn't ask for a more memory hierarchy and SIMD friendly algorithm. Today I am looking at 1M (larger) vectors and the full scan is still possible but I am using FAISS because it is a bird in the hand and I decided I can live with the tradeoff.

kristjansson 3y ago
I mean FAISS has IndexFlatL2 if you have it in hand and _want_ the full scan.

smokracek 3y ago

Does anyone have any recommendations for a decent crash course on using vector DBs in conjuction with LLMs? I wanna do some experimentation with getting a model to comment on the similarity of data vectors etc. and I don't really know where to start.

minimaxir 3y ago
If you want to experiment with vector stores, you can do that locally with something like faiss which has good multiplatform support and sufficient tutorials: https://github.com/facebookresearch/faiss https://github.com/facebookresearch/faiss Doing full retrieval-augmented generation (RAG) and getting LLMs to interpret the results has more steps but you get a lot of flexibility, and despite what AI influencers say there's no standard best-practice. When you query a vector DB you get the most similar texts back (or an index integer in the case of faiss), you then feed those result to an LLM like a normal prompt, which can be optimized with prompt engineering. The codifer for the RAG workflow is LangChain, but their demo is substantially more complex and harder-to-use than even a homegrown implementation: https://minimaxir.com/2023/07/langchain-problem/ https://minimaxir.com/2023/07/langchain-problem/
- marcyb5st 3y ago
  Also, if what you look up has no semantic meaning like parts number you might be better off with an inverted index in addition to ANN lookups. Especially if the embedding model has been trained on a dataset that is not similar to what you use it for. That's a common situation right now with embedding models based on LLMs.
pokpokpok 3y ago
I recommend pgvector, it's simple and well featured with good example code. Once you have a dataset of vectors loaded in, the next step is called rag / retrieval augmented generation
deleted 3y ago
[deleted]
malaya_zemlya 3y ago
deeplearning.ai has a short coursee on the topic https://www.deeplearning.ai/short-courses/large-language-models-semantic-search/ https://www.deeplearning.ai/short-courses/large-language-mod...
alumic 3y ago
You might also check out this previous thread on the subject. It offers some pretty fascinating discussions: https://news.ycombinator.com/item?id=35826929 https://news.ycombinator.com/item?id=35826929
bobvanluijt 3y ago
(I’m affiliated with Weaviate) You might want to check out this getting started guide. It takes a couple of minutes, and you're good to go https://weaviate.io/developers/weaviate/quickstart https://weaviate.io/developers/weaviate/quickstart

dmezzetti 3y ago

If you want an easy way to evaluate Faiss, Hnswlib and Annoy vector backends, check out txtai - https://github.com/neuml/txtai https://github.com/neuml/txtai. txtai also supports NumPy and PyTorch vector storage. Disclaimer: I am the author of txtai

Scene_Cast2 3y ago
Would you have any quick links or data on how they compare in terms of speed and recall?
- dmezzetti 3y ago
  https://ann-benchmarks.com/ https://ann-benchmarks.com/ is a good resource covering those libraries and much more.

daturkel 3y ago

Annoy came out of Spotify, and they just announced their successor library Voyager [1] last week [2]. [1]: https://github.com/spotify/voyager https://github.com/spotify/voyager [2]: https://engineering.atspotify.com/2023/10/introducing-voyager-spotifys-new-nearest-neighbor-search-library/ https://engineering.atspotify.com/2023/10/introducing-voyage...

gregsadetsky 3y ago
Amazing, thanks for the reference! The biggest immediate useful difference that I see is that Annoy uses read-only index files (from the docs: "you can not add more items once the tree has been created" [0]), while Voyager allows you to call `.add_item` at any time (I just pip installed to double check and yes -- it's great). [0] https://github.com/spotify/annoy#summary-of-features https://github.com/spotify/annoy#summary-of-features
- PLenz 3y ago
  The great thing about Annoy is that you can write the index to disk and thus do big data work on tiny workers at the edge. I've never really seen anything else do the same.
  - gregsadetsky 3y ago
    Oh yeah, Annoy is definitely mmap'ed i.e. you can use the index without loading the index file into memory. And that's very useful. As far as I can see, Voyager requires you to load the index into memory and doesn't (yet?) do mmap. Which... would make sense since you can change the data after loading the index. So, Voyager index files are fully loaded in memory..? Do I have this right?

danbruc 3y ago

That sound pretty much like binary space partitioning [1] which is probably best known for being used in Doom to accelerate the rendering. Also, if you only search the leaf subspace that you query point lies in, then you can in principle be arbitrarily far off from the true nearest neighbor. [1] https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning

taneq 3y ago
Yeah, it looks pretty similar to me too. I haven’t read up on vector DBs but I wonder of k-d trees would be a better fit?
jhj 3y ago
k-D trees and BSPs don't work well in high dimensions (say >20 to 30 dims), since your true nearest neighbor is highly likely to lie on either side of any dividing hyperplane. If each dividing hyperplane separates a set of vectors into two roughly equal parts, then for N vectors you have something on the order of log2(N) separating planes in order to get down to a single vector per terminal node. But for, say, a billion vectors in a 100-dimensional space (and assuming something like a k-D tree where you partition each dimension at each level), you have only partitioned log2(10^9) ~= 30 dimensions this way, yet there are 70 other dimensions remaining through which you can travel to find your true nearest neighbor (the curse of dimensionality; in high dimensions everything is "near" everything else) that you have not checked if you are discarding subspaces along the way. This is a problem for other approximate methods as well though. IVF methods still do a form of partitioning (via Voronoi cells) but this is obtained by clustering the data so it is more attuned to the global structure of the data rather than greedy divide and conquer. But in IVF methods it is still possible that you need to check every IVF cell in order to find your true nearest neighbor, just that it is less likely to happen in practice because the partitioning is more attuned to the overall structure of data rather than via greedy subdivision.
- esafak 3y ago
  And LSH uses random hyperplanes.

naillo 3y ago

This is so overcomplicated. You don't need an actual tree that's just a mental model. All you need to do is generate N random hyperplanes (defined via it's normal i.e. generate N normalized vectors in the dimension of your choosing). Then you generate a hash via these by going normal by normal and checking if your query vector `q` is on the left or right side of the normal by checking the sign of the dot product. I.e. `hash = [sign(dot(q, n1)), sign(dot(q, n2)), ...]`. So given a query you find that hash and you get all the vectors with the same hash (using your favorite hash to array data structure, i.e. a dict) and you can further refine the search within that bucket. It's like 10 rows of code.

rozim 3y ago
Sounds like you're describing LSH (locality sensitive hashing).
bigbillheck 3y ago
> All you need to do It seems to me that your approach is making some assumptions about how the data is distributed that aren't necessarily guaranteed to hold in practice, and a tree has a chance of being robust to at least some of those. For example, whatever random hyperplane you choose has to be informed by your data. Suppose you make a particularly bad choice for one of those hyperplanes, with your approach you'll be stuck with that for all time and have a bit in your hash that's biased to heck, but in the tree approach you only suffer when you hash your way down to the lousy node, and all other paths will be unaffected.
erikbern 3y ago
Annoy author here. What you're describing is Locality Sensitive Hashing (LSH) which is something I spent a lot of time trying back in 2009-2012 but never got it working. It has some elegant theoretical properties, but empirically it always has terrible performance. The reason I don't think it works well is that data often lies near a lower-dimensionality manifold that may have some sort of shape. LSH would "waste" most splits (because it doesn't understand the data distribution) but using trees (and finding splits such that the point set is partitioned well) ends up "discovering" the data distribution better. (but HNSW is generally much better than this tree paritioning scheme)

superdug 3y ago

I was so saddened by this title.. I thought there was a way to find annoying neighbors (at homes I’m interested in acquiring) and assumed this was a service for literally finding nearby annoy[ing] neighbors. To then go through the comments and find that this is a service with a minimum input of addresses and census data which are both freely available as is this service. Bravo hn!

debo_ 3y ago

When I saw the "oh yeah" I assumed this was going to be a deepfake Macho Man Randy Savage explaining ANN. I am disappointed.

lootsauce 3y ago

This popped up in the new feed yesterday and seems significant in the ANN space https://news.ycombinator.com/item?id=38054537 https://news.ycombinator.com/item?id=38054537

lootsauce 3y ago
Found code for it https://github.com/microsoft/DiskANN https://github.com/microsoft/DiskANN