MMOOZZGG.com

Glossary

What is approximate nearest neighbor search

In short

Approximate nearest neighbor (ANN) search is a way to find, very fast, the vectors in a huge database that are closest to a query. The price is a small loss of accuracy: some of the true nearest neighbors may not appear in the results.

Search and RAG · approximate nearest neighbor

MMOOZZGG.com editorsChecked: 1 min read

For a child

In a big city, you look for the friend who lives closest to your school. You could visit every house and measure the distance to each one, but that would take a week. Or you could go straight to the blocks next to the school. Your friend is almost always there, though now and then you miss someone. Approximate nearest neighbor search works the same way: fast and almost always right.

In plain words

Search by meaning comes down to one task: among a huge number of sets of numbers, find those closest to the set of numbers for the question. If you compare the question with each one in turn, a big database answers too slowly. So the database is arranged in advance by a special scheme: similar records are linked into a network or split into groups. During a search, the system follows this scheme and checks only a small part of the records. Sometimes it misses the true nearest neighbor, but the answer comes in milliseconds. For example, a store with a huge catalog shows similar items at once while the buyer scrolls the page.

For business

Almost every vector database runs on this kind of search, and its settings directly affect cost and quality. Index parameters change the balance: higher recall means more memory and a slower answer. Graph indexes are fast but keep data in RAM, and at tens of millions of records this is a real server cost. Vector compression saves memory but lowers accuracy a little. Rebuilding the index after a bulk load takes time, so teams plan it in advance. A small database is fine with an exact full scan, and a very small one can go into the model whole through CAG. Sizing memory for the index is part of choosing a server for AI.

For a specialist

Approximate nearest neighbor (ANN) search relaxes exact k-NN search. The algorithm returns candidates that contain most of the true neighbors, in exchange for a sublinear query time. Quality is measured by recall@k against an exact full scan, and speed in queries per second. The method families are graph methods (NSW, HNSW), trees, locality-sensitive hashing (LSH) and inverted files with quantization (IVF, PQ). HNSW (Malkov and Yashunin, 2016) builds nested layers of proximity graphs, with sparser layers on top. A search goes from the top down, which gives a logarithmic growth of complexity, and a neighbor-selection heuristic helps on strongly clustered data. ANN-Benchmarks (Aumüller, Bernhardsson and Faithfull, 2018) compares implementations on standard datasets by a curve of “recall against queries per second”. In that work, on the GloVe dataset, HNSW was faster than the others at all recall values. The authors note that very different approaches give a similar balance of quality and speed. In practice you must also handle metadata filtering and index updates.

Example

A marketplace stores vectors for all product descriptions. When a buyer opens a product page, approximate search picks similar items in milliseconds, so the “similar products” block loads with the page.

Related terms

Questions and answers

How much less accurate is approximate search? You can tune it. Index parameters let you find almost all true neighbors at the cost of memory and speed, and you choose the balance by measuring recall on your own data.
What is HNSW? HNSW is a common approximate search algorithm that builds a multi-level graph of links between similar vectors. A search goes down the levels from the top and quickly reaches the nearest records.

Sources

Not sure whether your company needs this?

AI solutions map
Contact us