Kdistance

K-distance is a metric-based measure used in data analysis to describe the local density around a point. Given a dataset P in a metric space with distance function d, the k-distance of a point p in P is the distance from p to its k-th nearest neighbor in P without p. Equivalently, it is the radius of the smallest ball centered at p that contains at least k points from P (excluding p). The set of k nearest neighbors of p is denoted N_k(p).

Computation and interpretation: To compute the k-distance of p, distances from p to all other points are calculated, sorted, and the k-th smallest distance is taken as the k-distance. The value of k determines the scale of the local neighborhood: smaller k emphasizes very local density, while larger k captures a larger surrounding region. The k-distance defines the k-neighborhood N_k(p).

Applications: The concept is widely used in clustering and anomaly detection. In density-based clustering such as DBSCAN, a core point is identified by its neighborhood size with respect to a chosen k, and the core distance is often defined via the k-distance. In Local Outlier Factor (LOF) methods, k-distance is used to compute reachability distances and local densities, which feed into outlier scores. Outside of these, k-distance serves as a general building block for local density estimation and neighborhood-based analyses. See also k-NN.

Computational considerations: Naive computation scales quadratically with dataset size, O(n^2), since distances to all other points must be considered. Efficient implementations use spatial data structures (such as KD-trees or ball-trees) or approximate nearest-neighbor methods to accelerate queries, especially in low to moderate dimensions. The concept extends to any metric space with a defined distance function and to various distance definitions beyond Euclidean.