What is k-nearest neighbors (k-NN)?

K-nearest neighbors, usually abbreviated k-NN, is the version of nearest-neighbor search that asks for the k closest points to a query rather than only the single closest one, where k is a number chosen ahead of time — three, ten, a hundred, whatever the application actually needs. It’s simultaneously the name of a search operation, covered here, and the name of a classic classification algorithm built on top of that operation, and it’s worth being clear about which sense is meant in a given context, since the two are closely related but not identical.

How does asking for k results change the underlying search problem?

Extending nearest-neighbor search from “find the single closest point” to “find the k closest points” doesn’t change the fundamental nature of the problem — it’s still built entirely on computing distances between a query and a set of candidates — but it does change what bookkeeping the search needs to maintain along the way. Finding a single nearest neighbor only ever requires tracking one running best answer, updated whenever a closer candidate is found. Finding the k nearest neighbors requires tracking an entire ranked set of the k best candidates seen so far, updating that whole set — potentially evicting the current worst member — whenever a new candidate turns out to be closer than the current worst entry in the set. This is exactly the role a bounded top-k heap plays in a real implementation: a data structure specifically designed to maintain a running set of the k best items seen so far, letting a search efficiently check “is this new candidate good enough to make the cut” without needing to re-sort the entire set from scratch every time a new candidate is considered.

The value chosen for k has direct, practical consequences for both the cost of a search and how it gets used downstream. A larger k means more bookkeeping during the search itself, since a bigger result set has to be tracked and potentially updated at each step, and it generally means examining more of the dataset before the search can be confident it’s found the true k best candidates. It also changes what the results are useful for: a small k, like one or five, tends to suit applications wanting a short, confident list of best matches, while a much larger k, sometimes in the hundreds, often serves as an initial, broader candidate generation step meant to be narrowed down further by a separate reranking process rather than being presented as a final answer on its own.

How does the k-nearest-neighbors classification algorithm relate to this same idea?

Separately from the search operation, k-nearest neighbors is also the name of one of the oldest and simplest algorithms in machine learning, used for classification and, in a related form, for regression. Given a labeled dataset — points where the correct category or value is already known — the k-NN classification algorithm predicts a label for a new, unlabeled point by finding its k nearest neighbors among the labeled data and having those neighbors effectively vote: the new point gets assigned whichever category is most common among its k closest labeled neighbors, on the reasoning that points close together in the underlying feature space tend to share the same category more often than not.

The connection between this classification algorithm and the search operation this documentation is primarily concerned with is direct and mechanical: the k-NN classification algorithm needs a k-nearest-neighbors search as its core subroutine, and everything covered throughout this documentation about making that search fast and scalable applies just as much to a k-NN classifier’s underlying search step as it does to any other application of nearest-neighbor search. It’s worth being aware of this dual usage of the term, though, since someone encountering “k-NN” in a machine learning context is likely discussing the classification algorithm as a whole, while someone encountering it in a vector database or search-engine context is almost always referring to the underlying search operation this documentation is centered on.

Why does k-NN search remain relevant even once approximate methods like HNSW enter the picture?

Everything HNSW does is still, fundamentally, in service of answering a k-nearest-neighbors query — the difference approximate methods introduce isn’t a change to what question is being asked, but a change to how confidently the answer can be guaranteed to be exactly correct. An exact k-NN search checks enough of the dataset to guarantee that the k results returned really are the true k closest points, full stop. HNSW‘s greedy, best-first traversal returns a set of k results that are very likely to be the true closest points, or very close to them, without offering that same absolute guarantee — which is precisely the trade-off recall exists to quantify, measuring what fraction of the true k-nearest neighbors an approximate search actually managed to find. Understanding k-NN as the precise underlying question being asked makes it much easier to understand exactly what recall is measuring: how well an approximate search’s answer to that k-NN question matches the answer an exact search would have given.

Having covered both senses of k-nearest neighbors and how the value of k itself shapes both search cost and downstream usage, the top-k search and bounded top-k heap glossary pages are worth reading next, since they go deeper into the specific mechanics of maintaining a ranked result set during a search. From there, the exact nearest-neighbor search and approximate nearest-neighbor search pages pick up the correctness-versus-speed trade-off introduced here, laying out exactly what’s being traded away when a system like HNSW is chosen over a method that guarantees exact k-NN results.