The Problem with "Exact"
Imagine you have a library with one billion books, and you want to find the book most similar to the one you're holding. In a regular database, finding an exact match is like looking up a word in a dictionary — fast and predictable. But finding the most similar item is fundamentally different: there's no shortcut. You have to compare your book against every other book in the library, one by one.
This is the core challenge of vector search. A vector is a list of numbers that encodes the meaning of something — a sentence, an image, a product. When you search for "similar" items, you're computing the geometric distance between your query vector and every stored vector. In a standard database, a B-Tree index finds an exact match in O(log N) time — logarithmic, meaning it barely slows down as data grows. Brute-force vector search is O(N) — linear, meaning it slows down in direct proportion to your dataset size.
At scale, the numbers become brutal. OpenAI's text-embedding-3-small model produces vectors with 1,536 dimensions. If you have one billion such vectors and a user submits a query, your system must perform roughly 1.5 trillion floating-point multiplications — just for that single query. On modern hardware, that takes seconds. For a real-time AI application, seconds is a death sentence.
The deeper problem is called the Curse of Dimensionality: as the number of dimensions grows, the geometric intuition we rely on breaks down. In high-dimensional space, all points tend to become roughly equidistant from each other. This means that traditional spatial indexing tricks (like k-d trees, which work beautifully in 2D or 3D) degrade to brute force performance above roughly 20 dimensions. At 1,536 dimensions, they are completely useless.
Approximate Nearest Neighbors (ANN)
The engineering solution is to stop insisting on perfection. Approximate Nearest Neighbor (ANN) algorithms accept a small, controlled probability of error — perhaps returning the 2nd or 3rd closest match instead of the absolute closest — in exchange for query speeds that are 100x to 10,000x faster than brute force.
The key metric for measuring this trade-off is Recall@K: of the true K nearest neighbors, what fraction did your ANN algorithm actually return? A Recall@10 of 0.95 means that for every 10 results returned, 9.5 on average are genuinely in the true top-10. For most AI applications — semantic search, recommendation engines, RAG pipelines — a Recall of 0.90 to 0.99 is indistinguishable from perfect in practice.
Two dominant algorithmic families power modern vector databases:
- Graph-based (HNSW): Navigates a multi-layer graph to find neighbors quickly. Prioritizes speed and recall.
- Clustering + Compression (IVF-PQ): Divides the space into regions and compresses vectors. Prioritizes memory efficiency and scalability.
Understanding both — and their hybrid combinations — is essential for designing AI infrastructure that actually works at production scale.