Approximate nearest neighbor algorithm

As explained in Building Reliable AI Systems

A search method that efficiently finds vectors close to a query vector while allowing approximate rather than exact nearest neighbors.

An approximate nearest neighbor (ANN) algorithm finds vectors close to a query vector without comparing the query against every stored vector. It trades exact nearest-neighbor results for faster search over large collections. In a listing search system, ANN retrieves semantically similar candidates; price and date filters then enforce explicit constraints, and a final ranker decides what to show. section 4.5.1 section 4.2.6

A production search pipeline can separate work that happens before a query from work that must happen during it:

• Generate and store listing embeddings in a vector database when listings are created or updated, without making users wait for that work. section 4.2.6
• Embed the incoming query, run ANN search for semantic candidates, apply traditional filters, then rank the remaining results using semantic similarity and other factors. section 4.2.6

Hierarchical Navigable Small World (HNSW) is one way to implement ANN search. Its index connects vectors in layers, from a sparse upper graph to a bottom layer containing all vectors. Search follows connections toward the query at one layer, then descends to refine its choice. This avoids the full O(n) scan required by naive nearest-neighbor search; the described HNSW approach has O(log n) search complexity. Index settings make the speed–quality trade-off operational: increasing M, the maximum connections per node, or efConstruction, the thoroughness of index building, can improve accuracy while using more memory or taking longer to index. Values of 16 and 100, respectively, are suggested starting points rather than substitutes for testing. section 4.5.1

Figure 4.7 HNSW indexes vectors in multiple layers. The search path demonstrates how queries efficiently traverse from sparse upper layers to dense lower layers.

The layered index and search path make it easier to see how HNSW narrows the search without scanning every vector. section 4.5.1

Evaluate ANN as part of the whole search experience, not just as an isolated retrieval step. Ranking accuracy matters, but booking conversion, user satisfaction, and results for long-tail queries show whether the complete pipeline helps users. section 4.2.6

How Building Reliable AI Systems covers it

How deep it goes

Explains HNSW’s layered graph traversal and index-tuning trade-offs, without giving a code implementation.

Examples

Uses listing search with price and date filters, plus an HNSW diagram tracing a search through graph layers.

What it assumes

Assumes queries and stored items can be represented as embeddings; introduces HNSW graph navigation conceptually.

What you can do after

Operate/configure HNSW by weighing M and efConstruction against search quality, memory use, and indexing time.

How it connects

Connects ANN to embeddings, vector databases, HNSW, explicit filters, and ranking.

liveBookmanning.com

Read Building Reliable AI Systems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  AI-Powered SearchApproximate nearest neighbor search is a retrieval technique that finds vectors likely to be nearest to a query vector while reducing the computations required for exact nearest-neighbor search.
• 

  liveBookmanning.com
  Natural Language Processing in Action, Second EditionAn approximate nearest neighbor algorithm finds items near a query vector with lower computational cost than exhaustive exact search while allowing some accuracy loss.
• 

  liveBookmanning.com
  MongoDB 8.0 in Action, Third EditionApproximate nearest neighbor search retrieves vectors near a query vector using an efficient approximation rather than exhaustive comparison.
• 

  liveBookmanning.com
  Outlier Detection in PythonA search technique that finds points near a query point with lower computational cost than exact nearest-neighbor search by allowing limited approximation.

Compare how 5 books explain approximate nearest neighbor algorithm →

Related concepts

• vector databaseused by · A vector database is a data-management system that stores and indexes numerical vector representations and supports retrieval through similarity or distance searches.
• HNSWimplemented by · HNSW is a graph-based approximate nearest-neighbor indexing and search method that organizes data points in a hierarchy of navigable proximity graphs.
• similarity searchcontrasts with · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.
• ivfflatimplemented by · IVFFlat is an approximate nearest-neighbor vector index that partitions vectors into centroid-based inverted lists and compares vectors within selected lists.

This explainer was generated by Manning's knowledge graph from the text of Building Reliable AI Systems. The section links point to the parts of the book it draws on.