HNSW

Exploring the path to fast nearest neighbour search with Hierarchical Navigable Small WorldsImage created by DALL·E 2 with the prompt “A bright abstract expressionist painting of a layered network of dots connected by lines.”Hierarchical Navigable Small World (HNSW) has become popular as one of the best performing approaches for approximate nearest neighbour search. HNSW is a little complex though, and descriptions often lack a complete and intuitive explanation. This post takes a journey through the history of the HNSW…

The best indexing approach for billion-sized vector datasetsPhoto by Paul Talbot on UnsplashWe learned about IVFPQ in the previous article, where the inverted file index (IVF) is combined with product quantization (PQ) to create an effective method for large-scale similarity search.In this article, we will learn about HNSW and how it can be used together with IVFPQ to form the best indexing approach for billion-scale similarity search.We will first introduce NSW and skip list, the two important foundations that HNSW is…