Vector Search (kNN)

Keyword, fuzzy, and prefix search all compare characters. None of them knows that car and automobile mean the same thing, because as strings they share almost nothing. To match meaning, you have to stop comparing characters and start comparing coordinates.

Picture a map where similar shops sit near each other: the cafes in one quarter, the hardware stores in another. To find what you want, you drop a pin and look at what is around it. Vector search turns text into exactly this kind of map, where meaning becomes location and "find something similar" becomes "find what is nearby".

Meaning becomes geometry

An embedding model takes a piece of text and returns a fixed-length list of numbers, a vector, usually a few hundred to a couple thousand of them (384, 768, and 1536 are common sizes). The model is trained so that texts with similar meaning get similar vectors: car and automobile land close together, car and banana land far apart. Nobody assigns those coordinates by hand; the model learns them from enormous amounts of text.

Once every document and every query is a vector in the same space, "find the documents most similar in meaning" turns into "find the vectors closest to the query vector." Meaning has become geometry, and search has become a distance problem.

Measuring nearness: two metrics

"Closest" needs a definition, and two show up everywhere:

• Euclidean distance: the straight-line distance between the two points. Small distance means near.
• Cosine similarity: the cosine of the angle between the two vectors, ignoring their length. A similarity of 1 means they point the same way, 0 means perpendicular. High similarity means near.

For text embeddings, cosine is the usual choice, because meaning lives in the direction a vector points, not in how long it is. A three-word query and a three-page document about the same topic should match, and cosine ignores exactly the length difference that would push them apart under euclidean distance. (Worth knowing: once vectors are normalized to unit length, which most systems do, cosine and euclidean rank neighbors identically, and a plain dot product is the fast way to compute the ranking.)

The angle is easier to feel than to read about. There is an interactive cosine explorer on the Visualizers page that lets you drag two vectors and watch the similarity move.

Exact nearest neighbor

With a metric chosen, the search is simple to state. To answer a query:

1. Embed the query into a vector.
2. Compute its distance to every document vector.
3. Sort, and return the k closest.

That is k-nearest-neighbor search, kNN, and done this way, by comparing against every vector, it is exact: you are guaranteed the true k closest, with no approximation anywhere.

Here it is in two dimensions. Every dot is a document; drag the query and its k nearest light up. Flip the metric and watch the neighbors change, because euclidean and cosine genuinely disagree about who is nearest:

A cloud of dots is abstract, so here is the same search on a small database you can actually read: a food menu laid out by flavor (savory to sweet, cold to hot). Pick a query phrase and watch kNN check every single item to find the match. The Graph toggle previews the faster approach from a later part; ignore it for now, or peek.

The wall

Exact kNN has one fatal problem, and it is step 2. Comparing the query against every document vector means N distance computations per query, each over d dimensions, so on the order of N × d multiply-add operations. For a thousand 768-dimensional vectors that is under a million operations, effectively instant. For a billion of them it is over 700 billion operations, per query, on every single query. Brute-force exact search simply does not scale, and scale is exactly where vector search is supposed to earn its keep.

The way out is to stop insisting on exact. If you accept the occasional near-miss, you can search a billion vectors in a few milliseconds. That trade, approximate nearest neighbor, is the subject of the next part, and it is what OpenSearch and every production vector database actually run.