Dense Vector Index

The core function of a dense vector index is to perform Approximate Nearest Neighbor (ANN) search. Unlike exact k-NN search, which is computationally prohibitive for billions of vectors, ANN algorithms trade a small amount of accuracy for massive gains in speed and scalability.

Key ANN algorithms include:

• Hierarchical Navigable Small World (HNSW): A graph-based method known for high recall and speed.
• Inverted File Index (IVF): Clusters vectors into Voronoi cells, searching only the most promising clusters.
• Product Quantization (PQ): Compresses vectors for in-memory efficiency, enabling billion-scale indexes.

These algorithms allow queries to execute in milliseconds even over datasets with millions to billions of vectors.

Dense vectors from modern embedding models (e.g., text-embedding-ada-002, BGE) typically have 512 to 1536 dimensions. This high dimensionality creates the "curse of dimensionality," where traditional spatial indexing (like B-trees) fails.

Indexes manage this by:

• Dimensionality Reduction: Using techniques like PCA to project vectors into a lower-dimensional space before indexing.
• Distance Metric Selection: Employing cosine similarity or inner product for text, and Euclidean distance (L2) for image embeddings. The index structure is optimized for the chosen metric.
• Vector Normalization: Storing unit vectors to simplify distance calculations and unify metrics.

Performance is dictated by where vectors reside in the storage hierarchy.

• In-Memory Indexes (e.g., FAISS flat index): Deliver the lowest latency (<1 ms) but are limited by RAM size. Suitable for datasets up to ~10-100 million vectors on large servers.
• On-Disk Indexes: Store compressed vectors on SSD/HDD. Much slower (10-100 ms) but can scale to billions of vectors. Often use memory-mapped files for efficient access.
• Hybrid Approaches (e.g., DiskANN, Qdrant): Keep a small, high-precision graph in RAM while storing full vectors on disk, balancing cost and speed.

Product Quantization is critical here, reducing vector size from 2-6 KB to ~128-512 bytes for in-memory operation.

Engineers tune search quality and speed via key parameters:

• ef or efSearch (HNSW): The size of the dynamic candidate list during graph traversal. Higher values increase recall and latency.
• nprobe (IVF): The number of Voronoi cells to search. Higher values increase recall.
• M (HNSW): The number of bi-directional links per node. Higher values create a denser, more accurate graph but use more memory.
• k: The number of nearest neighbors to return.

Tuning involves finding the optimal point on the recall-latency curve for a specific application. Production systems often target 95-99% recall at <50ms p95 latency.

Unlike static batch indexes, production vector indexes must handle CRUD operations with minimal downtime.

• Inserts: HNSW supports efficient online insertion. IVF indexes may require periodic re-clustering.
• Deletes: Often implemented as soft deletes (a filter mask) to avoid costly graph restructuring. Periodic compaction is required.
• Updates: Typically handled as a delete followed by an insert of the new vector.
• Persistence: Indexes must be serializable to disk. This involves saving the graph structure (HNSW), cluster centroids (IVF), and quantizers (PQ). Incremental checkpointing is used for fault tolerance.

Real-world retrieval requires combining semantic search with metadata filtering. For example: "Find documents about neural networks published after 2022."

Indexes support this via:

• Pre-Filtering: Apply metadata filters first, then run ANN search on the subset. Fast if the filter is highly selective.
• Post-Filtering: Run ANN search first, then filter the results. Can miss relevant items if they are filtered out post-search.
• Advanced Methods:
  • **HNSW with filters integrated into graph traversal.
  • **Bitmap indexes for fast metadata intersection.
  • **Scalar Quantization to store metadata within the vector payload.

This enables complex Boolean logic (AND, OR, NOT) on metadata fields alongside vector similarity.

HNSW is a graph-based algorithm for approximate nearest neighbor (ANN) search. It constructs a multi-layered graph where a search begins at a coarse, top layer and navigates to finer layers, providing a highly efficient and scalable search method with strong recall. It is a common indexing algorithm implemented in vector databases like Weaviate and the Faiss library.

• Key Property: Logarithmic time complexity for search.
• Use Case: The default index type in many production vector stores due to its speed/accuracy trade-off.

Hybrid search is a retrieval strategy that combines the results of sparse (keyword-based, e.g., BM25) and dense (vector similarity) retrieval methods. A weighted score fusion (e.g., reciprocal rank fusion) merges the ranked lists, leveraging the precision of lexical keyword matching with the semantic understanding of vector search. This approach mitigates the limitations of either method used alone.

Product Quantization is a lossy compression technique for high-dimensional vectors that dramatically reduces memory footprint for a dense vector index. It works by:

1. Splitting the original vector space into several subspaces.
2. Clustering vectors in each subspace to create a small codebook of centroids.
3. Representing each original vector by a short code (the index of its nearest centroid in each subspace).

This enables billion-scale vector indices to reside in RAM, with search performed using efficient lookup tables.

An Inverted File index for vectors is an ANN method that uses coarse clustering to narrow the search space. The process is:

• Training: Cluster the dataset into nlist Voronoi cells using k-means.
• Indexing: Assign each vector to its nearest cell centroid and build an inverted list mapping centroids to their member vectors.
• Search: For a query, find its nearest nprobe centroids and only search the vectors within those cells. This is often combined with Product Quantization (IVFPQ) in Faiss for large-scale search.