Similarity Search

Similarity search is the computational paradigm of retrieving objects from a dataset that maximally correlate with a given query vector under a designated metric space, such as Euclidean distance, cosine similarity, or inner product. As high-dimensional vector representations proliferate across modern computing—driven by deep learning embeddings for text, images, and audio—exact linear scanning becomes computationally prohibitive at scale. Consequently, production architectures rely on Approximate Nearest Neighbor (ANN) algorithms that trade marginal recall precision for logarithmic query latency. This specification details the mathematical foundations, algorithmic mechanics, and production-grade implementation of modern high-dimensional similarity search.

python3 -m venv venv
source venv/bin/activate
pip install --upgrade pip
pip install numpy faiss-cpu

import numpy as np
import faiss

# Set dimensional parameters and dataset size
np.random.seed(42)
dimension = 128
database_size = 100000
query_size = 5

# Generate synthetic high-dimensional embedding vectors (float32)
data_vectors = np.random.random((database_size, dimension)).astype('float32')
query_vectors = np.random.random((query_size, dimension)).astype('float32')

# Normalize vectors for cosine similarity via inner product metric
faiss.normalize_L2(data_vectors)
faiss.normalize_L2(query_vectors)

# Initialize HNSW index with M links per node and efConstruction parameter
# IndexHNSWFlat uses L2 distance; inner product is equivalent post-normalization
index = faiss.IndexHNSWFlat(dimension, 32, faiss.METRIC_INNER_PRODUCT)
index.hnsw.efConstruction = 64
index.hnsw.efSearch = 32

# Train and add vectors to the index
print(f"Building HNSW index for {database_size} vectors...")
index.add(data_vectors)
print(f"Total vectors indexed: {index.ntotal}")

# Execute similarity search
k = 3
scores, indices = index.search(query_vectors, k)

print("Search Results (Indices):")
print(indices)
print("Search Results (Inner Product Scores):")
print(scores)

import numpy as np
import faiss

def validate_recall(dim=64, n=10000, k=10):
    xb = np.random.random((n, dim)).astype('float32')
    xq = np.random.random((100, dim)).astype('float32')
    
    # Exact search baseline
    exact_index = faiss.IndexFlatL2(dim)
    exact_index.add(xb)
    D_exact, I_exact = exact_index.search(xq, k)
    
    # HNSW approximation
    hnsw_index = faiss.IndexHNSWFlat(dim, 16)
    hnsw_index.add(xb)
    D_approx, I_approx = hnsw_index.search(xq, k)
    
    # Calculate Recall@K
    matches = 0
    total = xq.shape[0] * k
    for i in range(xq.shape[0]):
        matches += len(np.intersect1d(I_exact[i], I_approx[i]))
        
    recall = matches / total
    assert recall >= 0.95, f"Recall@K fell below threshold: {recall}"
    print(f"Verification passed. Recall@{k}: {recall:.4f}")

validate_recall()

import faiss

# Limit OpenMP threads to prevent CPU thrashing in multi-process deployments
faiss.omp_set_num_threads(4)

# Implement safe index persistence
def persist_index(index, filepath):
    faiss.write_index(index, filepath)

def load_index(filepath):
    return faiss.read_index(filepath)

# Failure Mode Mitigation: Memory mapping large indices for zero-copy loading
# index = faiss.read_index("index.faiss", faiss.IO_FLAG_MMAP)

Mathematical Foundations & Metric Spaces

Similarity search operates within a metric space (X, d), where X denotes the vector space R^d and d represents a distance function satisfying identity, symmetry, and the triangle inequality. Common distance formulations include Euclidean Distance (L2), Cosine Similarity, and Inner Product (Dot Product). For normalized vectors where ||x|| = 1, inner product is monotonically related to squared Euclidean distance via d_L2^2(x, y) = 2 – 2 * <x, y>. The computational challenge arises because computing the exact distance from a query vector q to all n vectors in a dataset requires O(n * d) operations. As n scales to billions and d reaches 1536 or higher (common in modern transformer embeddings), exact linear scans violate real-time SLA constraints.

Algorithmic Paradigms: Quantization vs. Graph-Based Indexing

Modern Approximate Nearest Neighbor (ANN) search algorithms fall primarily into two paradigms:
1. Quantization-Based Methods (e.g., IVF-PQ): Inverted File Index with Product Quantization decomposes the high-dimensional space into Cartesian products of lower-dimensional subspaces. Vectors are quantized into compact centroid codes, reducing memory consumption drastically and enabling fast asymmetric distance computations.
2. Graph-Based Methods (e.g., HNSW): Hierarchical Navigable Small World graphs construct multi-layer proximity graphs where the bottom layer contains all data points and upper layers act as skip-lists for logarithmic routing. Greedy routing across layers navigates towards the query vector with sub-linear time complexity O(log n).

Engineering Considerations & Memory Bandwidth Bottlenecks

In high-throughput distributed systems, similarity search performance is rarely bound purely by arithmetic logic units (ALUs). Instead, it is bounded by memory bandwidth. Traversing graph structures involves non-contiguous memory access patterns, triggering CPU cache misses and Translation Lookaside Buffer (TLB) thrashing. Production architects must optimize vector layout (e.g., contiguous float arrays), utilize SIMD instructions (AVX-512, ARM Neon) for vector distance kernels, and choose quantization strategies (scalar quantization SQ8 or product quantization PQ) to fit working sets within L3 cache.