Graph-Based Index

Graph-based indexes are engineered to exhibit the small-world property, where most nodes can be reached from any other node in a very small number of hops. This is achieved by constructing a graph with long-range connections that act as shortcuts, preventing search from getting stuck in local neighborhoods. Algorithms like HNSW deliberately build a hierarchy of such graphs to enable logarithmic-time search complexity, making billion-scale searches practical.

Search is performed by starting at one or more entry points and iteratively moving to the nearest neighbor of the query within the current node's connections. This greedy, hill-climbing algorithm is simple but effective on a well-constructed graph. Performance is tuned using the search beam width parameter, which controls the size of the candidate pool during traversal. A wider beam explores more paths, increasing recall at the cost of higher latency.

The Hierarchical Navigable Small World (HNSW) algorithm enhances basic graph search by constructing multiple layers. The top layer is a sparse graph with few, long-range connections for fast navigation. Lower layers are progressively denser, containing more nodes and shorter-range connections for precise localization. Search begins at the top layer, quickly narrowing the region, before descending to lower layers for refinement. This hierarchy is key to achieving sub-linear query times.

The primary advantage of graph-based indexes is their ability to deliver very high recall (e.g., 95-99%) at millisecond-scale latencies for single queries. This performance profile is superior to many other ANN methods for a given accuracy-speed trade-off, especially on dense, high-dimensional data. The efficiency comes from the graph's direct encoding of proximity, allowing the search to prune irrelevant regions of the space without computing distances to all vectors.

Unlike some indexing methods that require full rebuilds, graph-based indexes typically support efficient incremental updates. New vectors can be inserted by finding their k-nearest neighbors in the existing graph and forming connections to them. This dynamic indexing capability is critical for real-time applications like streaming data or user-generated content. However, excessive deletions can fragment the graph, occasionally necessitating background optimization.

For optimal speed, the entire graph structure is held in RAM, leading to a significant memory footprint that scales with dataset size and graph connectivity. To manage this, algorithms like DiskANN optimize for scenarios where the index exceeds available memory. They store the graph on SSD and cache only a hot working set in RAM, using clever I/O scheduling to maintain high query throughput with a drastically reduced memory cost.

HNSW is the predominant graph-based algorithm for vector search. It constructs a multi-layered graph where the bottom layer contains all data points, and higher layers are progressively sparser subsets. This hierarchy enables extremely fast, logarithmic-time search via a greedy algorithm that starts at the top layer and navigates down. Key characteristics include:

• Probabilistic construction that ensures the small-world property.
• Tunable parameters for construction (M) and search (ef, efConstruction).
• Excellent performance on both high and low-dimensional data. It is the default index in many vector databases (e.g., Weaviate, Qdrant) and libraries like FAISS.

NSW is the foundational algorithm upon which HNSW is built. It constructs a single-layer graph by incrementally inserting nodes and connecting them to their nearest neighbors from the existing graph. Search is performed via a simple greedy traversal from a random entry point. While simpler, its limitations led to HNSW:

• Linear search time complexity on average, as lack of hierarchy can lead to long traversal paths.
• Serves as the building block for the bottom layer of an HNSW graph.
• Important for understanding the evolution and mechanics of modern graph indexes.

DiskANN is a graph-based index optimized for billion-scale datasets that exceed available RAM. Its core innovation is storing the graph structure and compressed vectors on SSD (Solid State Drive), while caching only a hot subset in memory.

• Uses a Vamana graph construction algorithm, related to HNSW but optimized for disk layout.
• Employs product quantization (PQ) to compress vectors, minimizing I/O.
• Delivers high recall and QPS (Queries Per Second) with a dramatically lower memory footprint than in-memory indexes. It is critical for cost-effective, large-scale search deployments where memory is a primary constraint.

FAISS (Facebook AI Similarity Search) is not an algorithm itself but a library that provides highly optimized, GPU-accelerated implementations of graph and other indexes.

• Its IndexHNSW and IndexHNSWFlat are standard implementations of the HNSW algorithm.
• Supports composite indexes like IndexHNSWPQ which combines HNSW with product quantization for memory efficiency.
• Provides tools for parameter tuning and benchmarking.
• Enables exact re-ranking of candidates retrieved from the graph. FAISS is the industry-standard toolkit for prototyping and deploying high-performance vector search.

NGT is an open-source library providing both graph and tree-based ANNS algorithms. Its graph component, PANNG (Path-based Approximate Nearest Neighbor Graph), uses a different construction philosophy:

• Focuses on optimizing search path length during graph construction.
• Offers tunable trade-offs between index build time and search accuracy.
• Provides commands for incremental insertion and batch deletion, supporting dynamic indexing.
• Often used in research and scenarios requiring fine-grained control over graph properties.

NMSLIB is a versatile, efficient library for similarity search in both metric and non-metric spaces. It implements several graph-based methods:

• HNSW as one of its primary methods.
• SW-graph (Small World Graph), another variant of the navigable small world concept.
• Known for its extensive benchmarking suite and support for custom distance functions.
• Often used as a performance baseline in research papers due to its robust, community-vetted implementations.

HNSW is the most prominent graph-based index algorithm. It constructs a multi-layered graph where the bottom layer contains all data points, and higher layers are progressively sparser subsets. This hierarchy enables extremely fast, logarithmic-time search by starting at a random node in the top layer and greedily navigating down through the layers. Its small-world property and scale-free connections make it the industry standard for high-recall, low-latency vector search.

ANNS is the overarching computational problem that graph-based indexes solve. It refers to algorithms that trade perfect accuracy for sub-linear search time in high-dimensional spaces. Key trade-offs include:

• Recall vs. Latency: Higher recall typically requires more computation.
• Index Build Time vs. Query Speed: Complex indexes take longer to build but query faster.
• Memory vs. Accuracy: Compression reduces memory but can introduce quantization error. Graph-based methods are one family of ANNS solutions, alongside hashing (LSH) and partitioning (IVF) approaches.

A small-world network is a graph where most nodes can be reached from any other node in a small number of hops, despite low average edge density. This property is deliberately engineered into graph-based indexes like HNSW. It is achieved by connecting each new node during construction to both its nearest neighbors (for exploitation) and to a few long-range "friend-of-a-friend" connections (for exploration). This structure is what enables the efficient, greedy traversal that finds near-optimal paths to the query's neighborhood.

Beam width (or efSearch) is a critical hyperparameter for graph traversal algorithms. It defines the size of the dynamic candidate list (priority queue) maintained during search. A larger beam width:

• Increases recall by exploring more parallel paths.
• Increases latency and memory usage per query.
• Reduces the risk of the greedy search getting stuck in a local optimum. Typical values range from 10 to 400, tuned based on the required recall-latency trade-off for the application.

Exact re-ranking is a hybrid search strategy often used with graph-based and other approximate indexes. The process is:

1. Candidate Retrieval: A fast, approximate index (e.g., HNSW) retrieves a broad set of candidates (e.g., 200-1000 vectors).
2. Re-scoring: This candidate set is re-evaluated using exact, full-precision distance calculations (e.g., Euclidean, cosine).
3. Final Ranking: The top-k results are selected from the re-scored list. This combines the speed of ANNS with the precision of exact search, crucial for applications where the final ranking must be perfect.

DiskANN is a graph-based index algorithm specifically optimized for billion-scale datasets that exceed available RAM. Its core innovation is storing the main graph index on SSD while caching a small, frequently accessed working set in memory. During search, it performs a greedy beam search on the in-memory cache, triggering sequential SSD reads to fetch neighboring nodes not in cache. This design achieves high query performance with a minimal memory footprint, making graph-based search feasible for massive datasets on single machines.