We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without any need for additional search structures, which are typically used at the coarse search stage of the most proximity graph techniques. Hierarchical NSW incrementally builds a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements. The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution. This allows producing graphs similar to the previously studied Navigable Small World (NSW) structures while additionally having the links separated by their characteristic distance scales. Starting search from the upper layer together with utilizing the scale separation boosts the performance compared to NSW and allows a logarithmic complexity scaling. Additional employment of a heuristic for selecting proximity graph neighbors significantly increases performance at high recall and in case of highly clustered data. Performance evaluation has demonstrated that the proposed general metric space search index is able to strongly outperform previous opensource state-of-the-art vector-only approaches. Similarity of the algorithm to the skip list structure allows straightforward balanced distributed implementation.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
This could of course be a bug, but it's worth noting that vector searching in general is a semantic ("meaning based") search technique, but it doesn't operate on the actual text, it operates on the resulting embedding so it may well make sense to include a (possibly fuzzy) full text search as well to catch literal instances of the text if that's what you actually need.
That said, the particular example you give may be either a configuration problem or just that "cat" is a particularly bad choice of word to use for a vector search in your corpus.
HNSW[1] is an approximate nearest neighbour search technique. So if you visualise the embedding as distilling your documents…
Read the full comment
down to a set of numbers, this vector forms the coordinates of a point in a high-dimensional vector space. HNSW is going to take the word "cat" in your example, embed that, and find what are probably the closest other vectors (representing documents) in that space by your distance metric.[2]
Now, it's easy to imagine the problem - if your document corpus is about something very unrelated to cats (like say your corpus is a bunch of programming books), the results of this search are going to be basically just random, because you have a big blob of embedded documents in your corpus which are relatively close together and your search term embeds way off in empty space and therefore the distance from the search term to any given document is extremely large. If you were to search a topic that is reflected in your corpus, your search term could embed right in the middle of that blob and the distances would be much more meaningful meaning the results are likely to be more intuitive and useful.
[1] https://arxiv.org/abs/1603.09320 is I think the original paper that introduced the technique
[2] The probably/approximately get out is what allows the computational complexity of HNSW to stay reasonable even if the corpus is large
the Hamming distance in the article is about twice the number of moves to get from one position to the other, mate in 4 is important?
A better criticism might be: this metric defines position as close even if can only be reached by reversing moves. There's some discussion in the HNSW paper https://arxiv.org/pdf/1603.09320.pdf of working with non-symmetric metrics but I haven't read further.
HNSW, or Hierarchical Navigable Small World is a graph data structure for approximate nearest neighbor search of vectors.
https://arxiv.org/abs/1603.09320
The problem space of ANN is one of those really deep holes you can go down. It’s a game of balancing time and space, and it’s got plenty of fascinating algorithms and datastructures.
Check out http://ann-benchmarks.com/ for a comparison. HNSW is not “the best” but it’s easy to understand and is quite effective.
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.