Hierarchical Navigable Small Worlds | Hacker News Reader

Hierarchical Navigable Small Worlds

pinecone.io

74 pointsgk114 comments

I wrote an HNSW implementation in pure Rust:

https://github.com/InstantDomain/instant-distance

It works pretty well for us at InstantDomainSearch.

I like to think that this is a fairly idiomatic Rust implementation so it might be easier to follow than Facebook's FAISS. It's kinda similar in design to FAISS, so I think it might achieve similar performance, though we haven't spent enough time benchmarking yet.

Are you using it for full text search over the available domain names? What are you using as the embedding layer to be typo tolerant?

We're mainly using it to find related names in the set of domains available from aftermarkets. We're using the fastText word vectors from Facebook for this. We haven't done any work specifically to deal with typos, although that's on our list.

You also have plenty of comments which makes it much easier to follow than the Faiss code - I wish I had found this a few weeks ago, thanks for sharing.

Tangential - the skip list example seems different from how I learned them in data structures. Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer?

> Wouldn't a better skip list have "down pointers" at each node so you don't have to retrace your work at each layer?

You don't have to retrace your work, per this example on 5 you could imagine there being implicit "down" pointers in that aggregate block, so you would go from L3 straight down to the data item once you hit that first logical element. This would be 2 I/O operations in my implementations.

Think:

  public class SkipListNode
  {
    public SkipListNode? Layer3;
    public SkipListNode? Layer2;
    public SkipListNode? Layer1;
    public SkipListNode Layer0;
  }

Once you find the one that has all 4 non-null, you can just grab the item at Layer0 without anymore searching.

I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastruc...), if you are trying to get an intuition here:

> we only allocate one pointer for every level of the skip list. In a typical skip list, a node will have a value, a pointer to the next largest element in the list and a pointer to the lower level of the skip list. This means that a new value allocated into the second level will require the space for two values and four pointers. We avoid this by always allocating skip list towers contiguously. Each level K pointer will only point to other level K pointers, so to extract the value associated with a level K pointer P, you read the value at P - K. Once you reach a node with a value greater than the one you are searching for, you go back to the previous node, and descend a level by simply subtracting one from the pointer. This lets us allocate a value into the second level by just consuming the space for the value and two pointers. It also reduces the amount of time we need to spend chasing pointers, because a pointer into a tower is likely to be on the same cache line as the lower pointers in that tower.

Skip lists are typically implemented with a short array of pointers at each node. When traversing a skip list in a loop the previous node is in a local variable. If you do it recursively the previous node is on the stack. "Retracing" is simply a matter of retrieving the previous node and adding 1 to the pointer array index.

Yes your explanation is correct, if it hits an end block or overshoot the target it returns to the previous block in the next layer (not the start block), I submitted a change to the article and visual to make this clear - should be updated soon. Thanks for pointing it out!

Very useful piece.

To the authors: there's a dangling TK ADD LINK comment that should have been removed before publication, I think.

Yes I missed that, thanks for pointing it out!

Hey I'm the author, feel free to ask me any questions!

thanks so much for writing this, unlike LSH there are very few articles on HNSW for some reason, while it's one of the most efficient (and relatively simple) nearest neighbors search methods out there. There is a precursor paper by HNSW author which explains the rationale and has interesting links to network science and neuroscience: https://arxiv.org/abs/1507.06529

I personally think both LSH and HNSW should be added to standard CS curriculum because of generality and so many immediate practical applications.

Yes that's why we wrote it! Other than in papers, finding info on HNSW is near-impossible so hopefully this will make a few lives easier.

I came across this paper when researching for the article, I agree the link to brain networks is fascinating

Reply on news.ycombinator.com