Published at Nov 29, 2024

HNSW vs. DiskANN

Written by Haziqa Sajid

Vector search powers many artificial intelligence (AI) applications by enabling fast, accurate retrieval of similar items, whether for recommendations, language understanding, or image processing. Given its wide range of applications, it is important to optimize vector search for scalability. Hierarchical navigable small world (HNSW) and disk approximate nearest neighbor (DiskANN) are prominent algorithms in this domain. HNSW leverages a multi-layered graph to achieve high search speed and accuracy, while DiskANN is designed to handle vast datasets efficiently by operating primarily on disk.

This article will help you understand how HNSW and DiskANN work, compare their strengths and limitations, and decide which best suits your AI and data needs. We will:

• Understand how HNSW and DiskANN algorithms function

• Compare performance and use cases for each

• Choose the right algorithm based on your system’s needs for speed and scalability

What Are Nearest Neighbor Search Algorithms?

Nearest neighbor search algorithms address the problem of finding vectors in a dataset that are most similar to a given query vector. In AI systems, data is often represented as vectors in a high-dimensional space, with the distance between vectors representing their similarity. This similarity is frequently measured using metrics like cosine similarity, which evaluates the angle between two vectors rather than their direct distance.

In practice, a user’s query is converted into a query vector, and the nearest neighbor search algorithm identifies stored vectors closest to this query vector, indicating high similarity.

Scaling challenges in nearest neighbor search

The scaling of nearest-neighbor searches presents significant challenges. Traditional or “greedy” algorithms calculate distances between the query vector and each vector in the database to determine the closest matches. While manageable for small datasets, this approach doesn’t scale well with large, AI-driven datasets where billions of vectors are common.

Because the query location is unpredictable, it’s not possible to pre-calculate or cache these distances. Instead, each new query requires fresh distance computations across all database entries, which is inefficient and limits the responsiveness needed in real-world applications. More advanced algorithms like HNSW and DiskANN are essential to achieve scalable, production-ready performance, as they offer optimizations tailored to handle large-scale vector search efficiently.

How HNSW Works

Hierarchical navigable small world (HNSW) is a graph-based nearest neighbor search algorithm designed to enhance search speed by creating an index structure based on the principles of the skip list. Inspired by the skip list’s layered probabilistic search, HNSW organizes data into a hierarchy of graph layers, where each layer has progressively denser subsets of data points. Before going into details of HNSW, let’s discuss its foundations:

1.  Skip lists: The foundation of layered search

At its core, HNSW builds upon the skip list search algorithm, a probabilistic approach to searching ordered data. Skip lists create random subset layers, allowing for increasingly refined searches. Like flipping through a book to find a specific page, skip lists let you make broad jumps first, then gradually narrow down to your target. Let’s see an example: 

An example of a skip list structure (Source)

To search for 71 in a skip list, start at the top left and move right, passing nodes like 31 since they're smaller. When you reach the end of a level, descend and repeat the process. Continue descending through the levels and moving right until you find 71. Here’s a guide if you are interested in learning more.

The beauty of skip lists lies in their simplicity. The algorithm can quickly navigate large datasets by creating multiple layers of the same data, with each upper layer containing fewer elements. While this method doesn't guarantee you'll find the exact match every time, it consistently achieves over 90 percent accuracy in returning the correct order of items.

2.  NSW: Graph-based navigation

The second key component is NSW (navigable small world), which tackles the challenge of finding nearest neighbors in vector space through graph-based navigation. Picture a vast network where each vector is connected to its nearby neighbors. The search process is intuitive: start at any point in the network, look at its connected neighbors, and move to whichever neighbor is closest to your query vector.

This process continues until you reach a point where none of the connected neighbors are closer to your query—this point is called a local minimum. While simple in concept, this approach provides an efficient way to navigate through vector space, especially when dealing with high-dimensional data. Here’s an example:

A simple illustration of a navigable small world

The search begins with node A as the predefined entry point. Node A selects node D, as the query is closer to D than to the nearer nodes C and B. At node D, the query is closer to node F. When no neighboring node is closer to the query than the current node, the search concludes, returning this final node as the result.

HNSW is an evolution of NSW that incorporates hierarchical multi-layer structures inspired by probability skip lists.

HNSW: The best of both worlds

HNSW brilliantly combines these two approaches by creating a hierarchical structure of NSW graphs. Imagine a series of layers containing its graph but with different information densities. The top layers are sparse, containing few vectors but allowing quick, broad searches. As you move through the layers, they become increasingly dense, enabling more precise searching.

The search process in HNSW is both elegant and efficient. You begin at the sparsest layer at the top, using the NSW graph search to find the closest vector at that level. Once you've seen this initial approximate match, you move down to the next, denser layer. Instead of starting from scratch, you begin your new search from the position you found in the layer above. This process repeats, with each layer refining your search further until you reach the bottom layer.

HNSW hierarchical layers speed up the search by quickly narrowing down the relevant area; dense lower layers refine the results for accuracy. Though fast and efficient, HNSW requires significant memory to manage multiple layers and maintain neighbor connections.

How DiskANN Works

DiskANN represents an innovative approach to approximate nearest neighbor search that challenges the conventional wisdom about ANN indices requiring main memory storage. While most ANN algorithms focus on in-memory performance, DiskANN introduces a novel architecture that enables efficient index storage on SSDs while maintaining competitive search performance.

The Vamana algorithm: A new graph-based approach

At DiskANN's core lies the Vamana algorithm, which takes a distinct approach to building navigable graphs compared to other methods like HNSW. While most graph-based algorithms start sparse and gradually add edges, Vamana begins with a dense random graph and employs an iterative pruning process to optimize it:

1. Initialize with a random graph having more edges than necessary

2. For each point in the dataset:

   • Perform a greedy search to find the current point's nearest neighbors

   • Use a "robust pruning" procedure to remove unnecessary edges while maintaining search efficiency

   • Add backward edges to ensure connectivity

3. Repeat the process twice, with different distance thresholds, to optimize local and long-range connections.

Progression of the graph by the Vamana indexing algorithm (Source)

This pruning-based approach allows Vamanato to balance graph diameter (which affects search depth) and degree (which affects memory usage) better than traditional methods. Vamana was chosen for DiskANN because it builds a flat graph, which performs better with disk storage than a hierarchical structure. 

With a flat graph, the exact location of each node’s neighbors can be pre-determined, making information retrieval faster and more efficient despite the slower nature of disk storage. This structure minimizes the performance loss typically associated with accessing data stored on disk.

Disk-based storage architecture

DiskANN's key innovation is its ability to operate efficiently from SSD storage rather than requiring the entire index to be loaded in memory. This is achieved through several clever design choices:

1. Clustered indexing: DiskANN partitions data into overlapping clusters using k-means clustering. Each data point belongs to multiple clusters, ensuring connectivity for search algorithms.

2. Compressed vectors in RAM: Stores compressed representations of vectors in RAM, while full-precision data is stored on SSDs, allowing fast initial comparisons in memory.

3. Beam search: DiskANN’s Beam Search retrieves neighborhood data from SSD in small batches, reducing read latencies by grouping nearby data access requests.

4. Caching frequently accessed data: Commonly accessed nodes are cached in RAM to minimize repeated SSD accesses, further enhancing speed.

5. Full-precision re-ranking: After identifying top candidates using compressed data, DiskANN re-ranks results using full-precision data from the SSD, ensuring accuracy without extra read overhead.

DiskANN's ability to operate from SSD storage represents a significant advancement in making ANN search more accessible and cost-effective at scale. While it may require more complex implementation and tuning compared to pure in-memory solutions like HNSW, the reduced memory requirements make it particularly valuable for:

• Large-scale production systems where memory costs are a concern

• Applications requiring billion-scale vector search on commodity hardware

• Scenarios where maintaining multiple indices in memory is impractical

The trade-off between slightly increased query latency and dramatically reduced memory requirements makes DiskANN an attractive option for many real-world applications. This is especially true for applications handling massive datasets that would be prohibitively expensive to serve entirely from memory.

Comparing HSNW and DiskANN

Now that we’ve explored both algorithms, let’s summarize their key points and compare them side by side in a table.

HNSW vs. DiskANN: A comparison

What Is Right for You?

Both HNSW and DiskANN offer excellent vector search performance, though each is better suited for different needs:

HNSW use cases

• Quick to scale: if you need vector search up and running quickly, HNSW is easier to implement, making it ideal for projects with tight timelines.

• Standard infrastructure: HNSW operates efficiently on typical hardware without additional configuration, which avoids complex setups.

• Memory-first approach: HNSW optimizes RAM usage, so it suits projects prioritizing in-memory speed over cost, particularly for mid-sized datasets.

• Cost flexibility: if compute costs aren’t an issue, HNSW’s RAM requirements are manageable, providing strong performance without strict cost constraints.

DiskANN use cases

• Compute efficiency: DiskANN’s design optimizes memory by leveraging SSDs, reducing RAM requirements, which is ideal for cost-sensitive projects.

• Designed for massive data: DiskANN is a solid choice when dataset sizes are too large for RAM, offering high performance on SSD storage.

• Advanced optimization potential: DiskANN enables complex configurations that can reduce costs over time—perfect for teams that can invest in longer-term optimization.

• Memory-to-disk transitions: It is suitable for organizations anticipating large data growth, allowing compute to shift from memory to SSD storage efficiently.

Alternatives to HSNW and DiskANN

Timescale has optimized DiskANN for PostgreSQL with pgvectorscale, focusing on SSD storage and accurate filtering for scalable, fast vector searches. Standard DiskANN relies on in-memory storage, which becomes costly for large datasets, and retrieval accuracy can degrade with post-filtering.

Key Innovations in pgvectorscale:

• SSD optimization: Traditional vector search algorithms require storing large data in RAM, which is costly. By integrating DiskANN, pgvectorscale allows vector data to be stored on SSDs, significantly lowering storage costs and maintaining high-speed search by reducing random memory access.

• Streaming retrieval: HNSW-based systems often faced accuracy issues when filters didn’t match pre-fetched results. Streaming DiskANN enables continuous retrieval, ensuring accurate filtering by fetching items until the desired results are met, overcoming the “ef_search” limitation.

• Statistical Binary Quantization (SBQ): Existing quantization techniques, like binary quantization (BQ), needed better accuracy. SBQ improves this by using a two-bit encoding for lower dimensions, enhancing recall and performance by enabling better differentiation and efficiency, especially for datasets with fewer dimensions.

These techniques collectively enable Timescale’s PostgreSQL extension to perform on par with specialized vector databases, enhancing affordability and compatibility with PostgreSQL’s ecosystem.

Conclusion

HNSW and DiskANN are highly efficient nearest-neighbor search algorithms, each excelling in different contexts. While their performance is similar in benchmarks, slight differences give each an edge depending on your needs. Timescale enhances your choice by integrating PostgreSQL's power and solving traditional indexes' limitations.

Discover more about Timescale's stack for AI and vector data and explore pgvectorscale to build scalable AI applications (GitHub ⭐s welcome).

Learn more

• Vector Data Basics: HNSW

• Understanding DiskANN

• Streaming DiskANN: How We Made PostgreSQL as Fast as Pinecone for Vector Data