4 ms·

Hierarchical Navigable Small Worlds

74 points by gk1 5y ago

jamesbriggs 5y ago
Hey I'm the author, feel free to ask me any questions!
andyxor 5y ago
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 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.
- jamesbriggs 5y ago
  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
akersten 5y ago
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?
- bob1029 5y ago
  > 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.
  - ntonozzi 5y ago
    I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastructure/2020/reducing-search-indexing-latency-to-one-second 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.
- dreamcompiler 5y ago
  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.
- jamesbriggs 5y ago
  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!
dochtman 5y ago
I wrote an HNSW implementation in pure Rust: https://github.com/InstantDomain/instant-distance 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.
- jamesbriggs 5y ago
  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.
- tlack 5y ago
  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?
  - dochtman 5y ago
    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.
archydeb 5y ago
Very useful piece. To the authors: there's a dangling TK ADD LINK comment that should have been removed before publication, I think.
- jamesbriggs 5y ago
  Yes I missed that, thanks for pointing it out!

74 points by gk1 5y ago

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 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.

jamesbriggs 5y ago
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

akersten 5y ago

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?

bob1029 5y ago
> 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.
- ntonozzi 5y ago
  I discussed this method a little more in a blog post (https://blog.twitter.com/engineering/en_us/topics/infrastructure/2020/reducing-search-indexing-latency-to-one-second 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.
dreamcompiler 5y ago
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.
jamesbriggs 5y ago
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!

dochtman 5y ago

I wrote an HNSW implementation in pure Rust: https://github.com/InstantDomain/instant-distance 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.

jamesbriggs 5y ago
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.
tlack 5y ago
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?
- dochtman 5y ago
  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.

archydeb 5y ago

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

jamesbriggs 5y ago
Yes I missed that, thanks for pointing it out!