Introduction to HNSW: Hierarchical Navigable Small World

Introduction

AI innovation is going on at breakneck velocity. One of many frontiers of this innovation is the vector engines like google. What are these engines like google, you ask? In easy phrases, they assist in coaching massive language fashions (LLMs) by going by means of massive datasets and selecting out what’s related. Now, there are lots of other ways during which this indexing is completed in vector databases. Amongst them, Hierarchical Navigable Small World (HNSW) stands out for being performant and scalable. All the most important vector shops present HNSW as an indexing technique. It’s quick, environment friendly, strong, and dependable. So, on this article, we are going to break down the interior workings of HNSW and study what makes it so quick.

Studying Targets

Perceive what embeddings and vector databases are.
Get conversant in the other ways of indexing in vector databases.
Study what HNSW is and the way it works.
Perceive HNSWlib, a header-only HNSW implementation.

This text was printed as part of the Information Science Blogathon.

What are Embeddings?

Embeddings are vector representations of knowledge (textual content, picture) in a high-dimensional vector house.

Two semantically associated information will likely be in proximity within the vector house, whereas dissimilar information will likely be far-off. In different phrases, the phrase embeddings for Messi and soccer will likely be shut collectively within the embedding house, whereas the phrase embeddings for soccer and Joe Biden will likely be far aside within the embedding house.

The size of vectors can vary from a couple of hundred to 1000’s or extra. This makes it tough to retailer, question, and search. However each Retrieval Augmented Technology (RAG) primarily based utility requires high-speed search and querying of knowledge embeddings. That is the place Vector Databases come into the image.

What are Vector Databases?

Simply as conventional databases goal to retailer structured and unstructured information, vector databases retailer, search, and question high-dimensional vector embeddings. They supply user-friendly interfaces to work together with embeddings and their related information. Vector databases usually are not basically completely different from conventional databases. Vector databases use conventional databases to retailer serialized embeddings. For instance, Chroma makes use of SQLite as in-memory storage, and Pgvector makes use of the Postgres database to retailer embeddings and their related metadata. The factor that separates a conventional database from a vector database is the underlying indexing algorithm.

Indexing in Vector Databases

Indexing refers back to the technique of organizing high-dimensional vectors in a method that gives environment friendly querying of nearest-neighbor vectors.

That is essentially the most essential a part of constructing any vector database. These indexes allow quick and environment friendly querying of high-dimensional embeddings. There are a number of indexing strategies to create vector indices, corresponding to:

Linear search Algorithm (Flat Indexing): It is a linear search algorithm, which implies it can evaluate the question vector with each different vector saved within the database. That is the best technique on the market and works nicely with small datasets.
Cluster-based algorithm (IVF): Inverted File is a cluster-based indexing approach. It makes use of k-means clustering to cluster all of the vectors. When a question vector is supplied, it calculates the gap between the question vector and the centroids of every cluster. And begins trying to find the closest neighbors within the cluster with the centroid closest to the question vector. This considerably reduces question time.
Quantization (Scalar and Product Quantization): The quantization approach includes decreasing the reminiscence footprint of huge embeddings by decreasing their precision.
Graph-based (HNSW): The most typical indexing technique. It makes use of hierarchical graph structure to index vectors. And that is what we’re going to discover.

Understanding HNSW

Massive language fashions (LLMs) have gotten more and more in style, and plenty of organizations need to implement them of their product stacks. Nonetheless, there’s a problem to doing this: LLMs have a restricted context window. A context window is the variety of tokens an AI mannequin can ingest. For instance, the GPT 3.5 turbo has a context size of 4096. That is the place vector search databases shine. As an alternative of throwing your complete e book into the context of LLM, we discover essentially the most related components and feed them to the LLM to get exact outcomes.

Now, amongst all of the other ways of indexing in vector databases mentioned above, HNSW is essentially the most strong and scalable. This makes it essentially the most broadly used indexing technique as nicely. HNSW is fashioned by combining two algorithms: skip record and navigable small world. To grasp HNSW, we have to know these algorithms. So, let’s dive in.

Skip Record

Because the identify suggests, the Skip record relies on the linked record information construction, or we will say it’s an extension of the linked record information construction. It was invented by David Pugh in 1990 as a quicker various to linked lists.

Why can we even want a skip record? A linked record has an O(n) search time complexity. This will not be very best for real-world use instances the place velocity of execution is paramount. So, this is the reason we may have a extra environment friendly linked-list algorithm.

The skip lists have an anticipated time complexity of O(log n). It performs a lot better at random entry than linked lists. Because it has a layered construction with a number of nodes at every layer, the worst-case house complexity is O(n log n), the place n is the variety of nodes on the bottom-most degree.

How Does Skip Record Work?

A Skip record maintains a layered linked structure the place the highest layer has the longest hyperlinks between components. This reduces exponentially as we transfer down the layers.

Within the above image, the bottom-most layer is an entire linked record. As we transfer up, the variety of nodes reduces by half in every layer. The construction is known as skip lists, as the upper layers allow you to skip nodes whereas traversing.

Contemplate the next instance.

When trying to find okay:

if okay = goal component
if okay >= transfer proper
if okay < transfer down

We begin from the highest left nook and transfer proper till we discover okay or a quantity lower than okay. We descend to the layer under and proceed the method till we attain okay. The search complexity is O(log n) as we skip half the objects at every degree.

Whereas random entry is quicker, insertion and deletion are slower as they add extra overhead for updating and deleting on a number of layers.

Whereas insertion, we begin from the underside record and add the node on the acceptable place. As skip lists preserve a hierarchical construction, we have to decide if the node seems at the next degree. The method is random, like a coin toss. The chance of a node showing in its quick higher layer is 0.5. In a great skip record, the variety of nodes on layer-1 will likely be ~n/2, and in layer-2 ~n/4, the place n is the variety of nodes on the bottom-most layer or the whole linked record.

Contemplate the next instance.

We discover the best place for insertion and insert the node on the backside degree. We then determine if the node seems on the higher degree primarily based on a random binary final result (heads or tail). In an ideal skip record, we get a balanced distribution of nodes in every degree.

Deletion occurs equally. Discover the goal quantity and delete the node. If the component is there on the next layer, delete it and replace the linked record.

Navigable Small World (NSW)

Navigable Small World is a graph-based algorithm for locating approximate nearest neighbors. The information factors in a graph are known as nodes. Every node is linked to a set set of connections which are shut to one another.

It is a grasping algorithm. It begins at a pre-defined level within the graph and selects nodes nearer to the goal node. The space between the nodes may be measured by Euclidean or Cosine similarity. This course of is repeated till it reaches the closest neighbors of the goal node.

The Navigable Small World algorithm could be very environment friendly and simply deployable. It really works nicely for datasets starting from a couple of hundred to 1000’s. After that, it tends to carry out worse. It suffers from pre-mature termination when it cannot discover a higher neighbor than the present one, because it makes use of solely native info to seek out the closest neighbor.

Throughout insertion, we traverse the graph to seek out the closest neighbors and join them to the node x.

As in vector databases, we have to take care of a number of thousands and thousands of embedding information. Therefore, we want a greater algorithm that scales nicely and affords higher searchability. Whereas NSW performs nicely sufficient for small datasets, we want a fair higher algorithm to deal with 100s of thousands and thousands or billions of knowledge factors. That is the place HNSW comes into the image.

Hierarchical Navigable Small World (HNSW)

HNSW extends NSW by incorporating the hierarchical structure of Skip Lists. This eliminated the scalability bottleneck of NSW. Like Skip Lists, HNSW creates the multi-layer construction of NSWs as an alternative of linked lists. Like Skip Lists, the topmost layer may have fewer information factors with the longest connections. The variety of components will increase as we transfer down the hierarchy. On the bottom-most degree, we’ve all the info factors. Like skip lists, the chance of the existence of a component exponentially decreases as we transfer up within the hierarchy.

However how can we search in HNSW?

Looking out in HNSW

Now recall each the skip record and NSW. Within the skip record, we begin on the uppermost layer, and in NSW, we begin at a pre-defined level. In HNSW, we begin from a pre-defined level on the uppermost layer of the hierarchy and greedily traverse the graph to seek out the closest component to the goal information level in that layer. As soon as we attain the closest node, we descend to the layer under and repeat the method till “Okay” nearest neighbors of the goal node are discovered. See under image

Insertion and Deletion in HNSW

Insertion in HNSW follows the identical precept as that of Skip lists. We traverse the layers, discovering the closest neighbors of the component. Then, we transfer down and repeat the identical course of till we discover all the closest neighbors on the underside layer.

The following process is to find out the bi-directional hyperlinks to the inserted component. It’s normally decided by a predefined parameter m. We join the m variety of nearest neighbors to the inserted node. This is likely one of the methods to find out connections to an inserted node. Different heuristics can be used. As an example, as an alternative of solely connecting to the closest neighbor nodes of the identical area, we additionally join the inserted node to the closest node of the closest area to kind a better-connected graph.

As with the skip lists, the chance of a node showing within the larger layers is determined randomly. The operate for it’s ground(-ln(rand(0, 1))), the place rand(0, 1) is a random quantity sampled from a uniform distribution between (0, 1].

Deletion follows the same strategy. We begin with the highest layer and delete the goal because it seems until the underside layer.

Complexities in HNSW

The time complexities of looking out, insertion, and deleting in HNSW depend upon a number of components, together with the peak of the structure, the variety of neighboring nodes per node, and the gap metric. However on common, looking out, insertion, and deletion have O(log n) time complexity. The development of the HNSW may be costly. We have to insert n variety of nodes with O(log n) complexity. So, the general time complexity of graph building will likely be O(n log n).

Vector databases are constructed to deal with a whole bunch of thousands and thousands of embeddings. Indexing such an quantity of knowledge requires a extremely environment friendly, strong, and scalable algorithm. HNSW ticks all of the packing containers.

Cons of HNSW

Though the looking out, insertion, and deletion are quicker in HNSW, there are a couple of trade-offs you must know earlier than going with HNSW. Right here are some things to remember earlier than implementing HNSW.

Larger Reminiscence footprint: HNSW maintains a hierarchical construction of embeddings, which considerably will increase reminiscence consumption in comparison with algorithms like NSW. This may be problematic for resource-constraint units.
Parameter Tuning: HNSW has completely different tunable parameters. Cautious parameter tuning is required to enhance efficiency.
Issue: Implementing HNSW from scratch can get tough. Most vector databases use trusted pre-built options corresponding to FAISS or HNSWlib.

HNSWlib is a header-only C++ implementation of the HNSW algorithm with Python bindings. It was written by the creator of the HNSW paper, Yury Malkov. It is a bare-bone implementation of the algorithm.

So, let’s get into it.

You may set up HNSWlib with any Python bundle supervisor.

pip set up hnswlib

Declare and Initialize HNSW index.

import hnswlib
import numpy as np
import pickle

dim = 16
num_elements = 100

hnsw_index = hnswlib.Index(house=”l2″, dim = dim) #declare Index
hnsw_index.init_index(max_elements = num_elements, ef_construction = 200, M = 16)

The house parameter is the gap metric that will likely be used to calculate the gap between nodes. Python implementation helps squared L2, Cosine, and dot-product.
The dim parameter is the dimension of embedding vectors
The init_index technique initializes the index.
ef_construction defines the development time/accuracy trade-off.
M is the variety of bi-directional hyperlinks created in the course of the insertion of a node.

Now that we created the indexes let’s add a couple of vectors.

data1 = np.float32(np.random.random((num_elements, dim)))
ids1 = np.arange(num_elements)
data2 = np.float32(np.random.random((100, dim)))
ids2 = np.arange(100)
data3 = np.float32(np.random.random((100, dim)))
ids3 = np.arange(100)

hnsw_index.add_items(data1, ids1)
hnsw_index.add_items(data2, ids2)

hnsw_index.set_ef(50) #set question time velocity/accuracy trade-off
hnsw_index.set_num_threads(4) #units variety of threads throughout batch building

Now, let’s see how we will question okay’s approximate nearest neighbor.

labels, distances = p.knn_query(information, okay = 1)

Serialize the index object utilizing pickle.

p_cp = pickle.hundreds(pickle.dumps(hnsw_index))

Deleting components.

for id in ids2:
hnsw_index.mark_deleted(id)

It will liberate the final 100 components from the index. If you want, you can too reuse the reminiscence of deleted components.

hnsw_index.add_items(data3, labels3, replace_deleted=True)

Conclusion

The HNSW is likely one of the most vital algorithms proper now for the event of vector retrieval strategies. It’s the major indexing algorithm utilized in all main vector databases. Hope you’ve understood the workings of HNSW by means of this text. As AI evolves, we are going to see the event of bigger and extra complicated studying fashions, inflicting an increase within the want for utilizing HNSW and growing its functions and significance.

Key Takeaways

Vector databases are purpose-built information shops for storing high-dimensional vector embeddings.
Indexing of embeddings permits vector shops to deal with querying, insertion, and deletion of embeddings.
There are other ways of indexing vectors, corresponding to IVF, Annoy, Quantization, and HNSW.
HNSW is a mixture of two algorithms. Skip lists and a Navigable Small World (NSW).

Continuously Requested Questions

The media proven on this article isn’t owned by Analytics Vidhya and is used on the Writer’s discretion.

Associated