Approximate Nearest Neighbour
Approximate Nearest Neighbour is a search method that very quickly finds entries similar to a queried entry within huge amounts of data. It deliberately forgoes the guarantee of finding the absolute best match, thereby becoming hundreds of times faster.
Computers often represent things like texts, images, or songs as long lists of numbers. Two such number lists can be compared: if they lie close together, the two things are similar. If you search for the most similar image to a given one within a collection, you are essentially searching for the number list with the smallest distance. With a billion stored entries, it takes too long to compute every single one. Approximate Nearest Neighbour, ANN for short, solves this problem with a compromise: the method only checks a small, cleverly selected part of the collection. As a result, it usually — but not guaranteed — finds the truly best match.
Why a bit of inaccuracy pays off
The exact search is called brute force: the query is compared with every single entry. The result is perfect, but the computing time grows directly with the amount of data. With ten million entries, such a search can quickly take several seconds. For a web search or a chatbot, that is unusable.
ANN reverses this relationship. Typical methods deliver answers within a few milliseconds, even with billions of entries. The price is the so-called recall rate: it indicates what percentage of the truly best matches were found. Common systems operate with 95 to 99 percent recall.
In practice, this loss is barely noticeable. If a music app suggests the third most similar song instead of the second most similar one, nobody notices. It’s a different story when completeness is legally required, for instance when researching court records. There, exact search remains the right choice.
How the shortcut through the mountain of data comes about
All ANN methods rely on the same idea: the data is organized beforehand so that large portions can later be skipped. This preparation is called index building and happens once. It can take hours, but afterward it saves time on every single query.
A common approach divides the data into groups of similar entries. For each group, the system remembers a center point. During a query, only the few center points are compared first. Then only the two or three nearest groups are thoroughly searched. The rest of the collection is not touched at all.
The most important approach today is called HNSW and works with a network of connections. Each entry is linked to several similar entries, like friends in a social network. The search starts at an arbitrary point and works its way toward ever-closer neighbours. Additionally, there is a coarse upper layer for long jumps, similar to a highway network above country roads. This way, the right region is reached in just a few steps.
ANN in search fields and AI chatbots
ANN is most commonly found in recommendation systems. Streaming services and online shops store a number list for each user and each product. The suggestion “You might also like this” is, at its core, an ANN search. The smartphone’s photo search also works this way, when it shows matching photos in response to the input “dog”.
In AI news, the term usually appears in connection with vector databases. These are databases built specifically for such similarity searches. Providers like Pinecone, Weaviate, or Qdrant are essentially selling a well-run ANN index.
This is especially important for chatbots that access company documents. This method is called RAG: before answering, the system searches for the matching text passages and presents them to the language model. This search step is an ANN query. A common misconception is therefore to consider ANN part of the AI model. It is purely a search technique and works entirely without neural networks.