An approximate nearest neighbor (ANN) algorithm finds vectors close to a query without comparing the query against every stored vector. It trades a small amount of precision for much faster retrieval, making semantic search practical for large collections of dense embeddings. section 4.8.1 section 10.3.4
ANN becomes useful when semantic search must handle:
- Large corpora, where exhaustive comparison requires O(N) vector operations for every query. section 4.8.1
- High-dimensional embeddings, such as BERT sentence vectors with 768 dimensions, where the curse of dimensionality increases search cost. section 10.3.4
- Production semantic search, where vector databases provide indexed retrieval and configurable speed–accuracy tradeoffs. section 10.3.3 section 10.3.5
Locality-sensitive hashing (LSH) is one ANN approach: it assigns vectors to regions of high-dimensional space so nearby candidates can be retrieved efficiently. ANN methods also include hash-based, tree-based, and graph-based families, each with different strengths and weaknesses. Choosing an ANN index is a central decision alongside choosing the embedding model. section 10.3.4 section 10.3.5
Semantic search over millions of documents
A search service for Wikipedia cannot afford dot products against six million articles for every query. An ANN index can return several close document vectors quickly, accepting that it may miss some exact best matches. PostgreSQL with pgvector can store and index vectors beside full-text indexes, supporting a hybrid search pipeline; vectors beyond its stated dimensionality limits require dimension reduction such as PCA. section 10.3.4 section 10.3.5
Figure 10.4 A visualization of three stages of the way the Annoy algorithm splits the search space using hyperplanes
Visualizes how Annoy progressively partitions a search space with hyperplanes, making the index’s candidate-selection idea easier to inspect. section 10.3.5
