“Nearest Neighbor Pattern Classification” by Thomas Cover and Peter Hart appeared in the IEEE Transactions on Information Theory in 1967. It gave a rigorous analysis of one of the simplest possible classifiers: to label a new data point, find the most similar stored example and copy its label.
The paper’s central result concerns how good this naive rule actually is. Cover and Hart proved that, given enough data, the error rate of the single nearest-neighbor rule is never worse than twice the best error rate any classifier could possibly achieve (the Bayes error). In other words, a method that does almost no work and makes no assumptions about the data still comes within a factor of two of the theoretical optimum. They also analyzed the k-nearest-neighbor generalization, where a point is labeled by a vote among its k closest stored examples.
This gave a respected theoretical home to an idea that remains widely used. Nearest-neighbor methods underpin recommendation systems, similarity search, and the retrieval step in modern vector databases, where finding the closest stored vectors to a query is the core operation.
Why business readers should care: nearest-neighbor search is the engine behind “find me items similar to this one,” from product recommendations to the document retrieval that grounds many AI assistants.