[HN Gopher] Parallelizing HNSW (Hierarchical Navigable Small Wor...
       ___________________________________________________________________
        
       Parallelizing HNSW (Hierarchical Navigable Small World) graphs
        
       Author : LukeEF
       Score  : 41 points
       Date   : 2024-01-02 12:16 UTC (10 hours ago)
        
 (HTM) web link (github.com)
 (TXT) w3m dump (github.com)
        
       | weeksie wrote:
       | Nice one, Gavin!
        
       | jasonjmcghee wrote:
       | Really appreciate this post. I've been thinking a lot about hnsw
       | and researching / playing with them.
       | 
       | Adding parallelization to the mix could really help with a
       | thought experiment I've been trying to tackle: if you wanted to
       | embed the entire internet in a way that's feasibly hostable and
       | updatable, how do you do it?
       | 
       | Well it sure can't live in RAM. And as the index gets large,
       | insertion gets very slow.
       | 
       | Let's leave the RAM bit aside for a bit.
       | 
       | So what if we cluster and have one index per cluster? Well it
       | turns out features often belong to multiple clusters, not one.
       | 
       | Ok so we soft cluster- but it turns out choosing the number of
       | clusters is also very hard. So maybe we use HDBSCAN.
       | 
       | Well that is very slow at scale too.
       | 
       | I talked about this on Twitter and Leland McInnes responded
       | suggesting UMAP (he's the lead author of both HDBSCAN and UMAP
       | papers - was a bit starstruck)
       | 
       | So if we now reduce dimensionality of embeddings with UMAP to say
       | 5 dimensions in order to create soft clusters with HDBSCAN and
       | create one hnsw index per cluster using the full / non-reduced
       | embeddings (consider a member to be a point where the cluster is
       | its kth most probabilistic).
       | 
       | And the problem is starting to get more tractable. Search
       | requires the umap step and calling predict proba on HDBSCAN to
       | find which k clusters / hnsw indices to search.
       | 
       | Now the problem is updating... What if we add a bunch of
       | documents and clusters are effectively different? Seems like
       | either you need to start with a representative sample so you
       | don't need to rebalance, or come up with a reclustering step. The
       | MST of HDBSCAN might simplify this.
       | 
       | So the RAM thing- yeah. Well, now that we have a bunch of
       | individual cluster-based indices, we only need to load the ones
       | the current search requires.
       | 
       | And we might not even need to do that. I built this approach I
       | called "portable hnsw" that actually served the indices as
       | parquet files which supports range requests, so you don't even
       | need to load the whole thing into memory. (Unless you want to
       | update the index)
       | 
       | Really interested in your thoughts.
        
         | ggleason wrote:
         | Those are all interesting ideas.
         | 
         | For the index structure itself you can use succinct dynamic
         | data structures to reduce the size. The bulk loading approach
         | is particularly amenable to use of succinct data structures as
         | the node-vectors in a HNSW are montonic they can use an Elias-
         | Fano encoding. The neighborhoods can use log-arrays.
         | 
         | Creating a multi-index also seems possible, where you use the
         | triangle-inequality to prune the candidate vectors. This will
         | probably require storing the distances for neighbor distances
         | in the bottom layer, in order to be time-efficient for query
         | and would thereby be slightly bigger. I haven't tried it yet
         | but I intend to.
         | 
         | There is also the possibility of using random projection for
         | dimensionality reduction. I also haven't tried this yet either
         | but will give it a go soon. We haven't folded the parallel hnsw
         | into our open source VectorLink yet, but we'll be doing it in
         | the near future - we wanted a little bit of stability of
         | approach first.
        
           | jasonjmcghee wrote:
           | I'm going to need to research to understand most of what you
           | said here before being able to give a coherent response.
           | Thanks for giving me an opportunity to learn!
        
       | speps wrote:
       | Typo both on HN and TFA. It's "hierarchical".
       | 
       | Reminds me of when there's a typo in a codebase and the auto
       | completion just replicates it across everywhere.
        
       | justinclift wrote:
       | This seems to be related, as in being an implementation for
       | PostgreSQL:
       | 
       | https://news.ycombinator.com/item?id=38844945
        
       ___________________________________________________________________
       (page generated 2024-01-02 23:01 UTC)