Beyer, K., Goldstein, J., Ramakrishnan, R. and Shaft, U. (1999). When is “nearest neighbor” meaningful? In Database Theory — ICDT’99, LNCS 1540, pp. 217–235. DOI 10.1007/3-540-49257-7_15
Key takeaways
Read in full (NOTE-917). For a fixed number n of data points and a query drawn independently of them, if the variance of the p-th power of the query-to-point distance, divided by its mean, goes to zero as dimension m grows, then the farthest point is, with probability tending to one, within any factor 1 + ε of the nearest (Theorem 1). The condition holds for IID dimensions and for several correlated or non-identical workloads, and fails when data and queries lie on a low-dimensional subspace or when queries fall inside well-separated clusters. Simulations put the collapse of contrast within 10 to 20 dimensions for IID data, and two real image-feature sets showed weak contrast. The condition is sufficient, not shown necessary; the theorem is about the ratio of distances with n held fixed, and says nothing about real data of low intrinsic dimension except that such data can escape it.
Why this is here
CLAIM-310 and QUESTION-114: under a variance condition on data and queries jointly, the nearest and farthest neighbours become nearly equidistant as dimension grows. The condition is sufficient only, and clustered queries, near matches and data with few latent degrees of freedom escape it; the paper’s remedy for clustered data is to return the whole nearest cluster.