nearestneighbor

Nearest neighbor is a family of algorithms and concepts used to identify the closest data point to a given query within a dataset, according to a defined distance or similarity measure. The basic problem is to find the single point with the smallest distance to the query; a related formulation, k-nearest neighbors (k-NN), uses the k closest points for decision making in classification or regression.

Distance metrics vary: Euclidean distance, Manhattan distance, cosine distance, and Mahalanobis distance are common. The choice depends on data properties and the task. For static datasets, data structures such as kd-trees, ball trees, cover trees, or VP-trees can speed up exact searches by organizing data spatially. For large-scale or high-dimensional data, exact search becomes costly, and approximate nearest neighbor (ANN) methods are preferred.

ANN methods include locality-sensitive hashing (LSH), product quantization, and graphs like HNSW, FAISS, and Annoy. These provide probabilistic guarantees of returning a nearby point rather than the exact nearest. Complexity: exact search is typically O(n d) per query; using structures can reduce query time at the cost of preprocessing and occasional incorrect results in ANN.

Applications span image and text retrieval, pattern recognition, recommender systems, geospatial queries, and anomaly detection. Nearest neighbor methods are valued for their simplicity and nonparametric nature, but practical use requires balancing exactness, speed, and memory requirements through appropriate distance measures and data structures.