[HN Gopher] Hierarchical Navigable Small Worlds
       ___________________________________________________________________
        
       Hierarchical Navigable Small Worlds
        
       Author : gk1
       Score  : 47 points
       Date   : 2021-10-06 11:24 UTC (1 days ago)
        
 (HTM) web link (www.pinecone.io)
 (TXT) w3m dump (www.pinecone.io)
        
       | akersten wrote:
       | 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 wrote:
         | > 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 wrote:
           | 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.
        
       | andyxor wrote:
       | 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.
        
       | dochtman wrote:
       | 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.
        
         | tlack wrote:
         | 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?
        
       | archydeb wrote:
       | Very useful piece.
       | 
       | To the authors: there's a dangling TK ADD LINK comment that
       | should have been removed before publication, I think.
        
       ___________________________________________________________________
       (page generated 2021-10-07 23:01 UTC)