liveBook · Manning

Brute-force similarity search

As explained in Retrieval Augmented Generation, The Foundational Ideas

Brute-force similarity search compares a query vector with every vector in a dataset to identify the most similar items.

Brute-force similarity search compares a query vector with every database vector, typically through dot products, to return exact nearest neighbors. Its cost is O(n × d), where n is dataset size and d is vector dimensionality. section 2.2.1

Its practicality depends on scale and response-time requirements:

  • Small catalogs can support exact scans: roughly 6,500 128-dimensional movie embeddings require fewer than one million floating-point operations per query. section 2.2.1
  • Enterprise catalogs make real-time exact scans impractical; billion-scale search therefore shifts toward Approximate Nearest Neighbor algorithms. section 2.2.1
  • GPU acceleration can keep exact search practical for large applications, but latency, recall, and memory still require measurement. section 2.2.3

From a movie catalog to a global catalog

A single query can scan Netflix’s roughly 6,500-movie domestic catalog quickly, while scanning Amazon’s then-more-than-200-million-item global catalog in real time becomes unusable. section 2.2.1

Figure 2.2 What cosine similarity measures and discards. Top left: the query and doc A sit at angle θ, and doc B, twice as long and pointing the same way, scores identically, because normalizing removes magnitude before the dot product. The other three panels draw the values listed above: identical direction scores 1.0, right angles score 0.0, and opposite directions score −1.0, which text embeddings almost never produce.

Shows how normalized vectors use direction for cosine similarity, including identical, orthogonal, and opposite directions. section 2.2.1

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Defines vector comparison and O(n × d) cost, then stops short of implementation details and defers large-scale retrieval to ANN methods.
Examples
Contrasts a 6,500-movie Netflix catalog with Amazon’s then-more-than-200-million-item global catalog.
What it assumes
Introduces vectors, normalization, cosine similarity, and dot products before applying them to similarity search.
What you can do after
Evaluate when exact similarity scans meet latency and scale requirements and when ANN or GPU acceleration becomes necessary.
How it connects
Connects vector embeddings, dot products, cosine similarity, Approximate Nearest Neighbor search, FAISS, GPUs, and RAG.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.