to be fixed, but the query point is arbitrary. All nearest neighbors For some applications (e.g. entropy estimation), we may have N data-points and wish to know which is the nearest neighbor for every one of those N points. This could, of course, be achieved by running a nearest-neighbor search once for every point, but an improved strategy would be an algorithm that exploits the information redundancy between these N queries to produce a more efficient search. As a simple example: when we find the distance from point X to point Y, that also tells us the distance from point Y to point X, so the same calculation can be reused in two different queries. Given a fixed dimension, a semi-definite positive norm (thereby including every Lp norm), and n points in this space, the nearest neighbour of every point can be found in O(n log n) time and the m nearest neighbours of every point can be found in O(mn log n) time. See also Ball tree Closest pair of points problem Cluster analysis Content-based image retrieval Curse of dimensionality Digital signal processing Dimension reduction Fixed-radius near neighbors Fourier analysis Instance-based learning k-nearest neighbor algorithm Linear least squares Locality sensitive hashing Maximum inner-product search MinHash Multidimensional analysis Nearest-neighbor interpolation Neighbor joining Principal component analysis Range search Similarity learning Singular value decomposition Sparse distributed memory Statistical distance Time series Voronoi diagram Wavelet References Citations Sources Further reading External links Nearest Neighbors and Similarity Search – a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits Similarity Search Wiki – a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours Approximation algorithms Classification algorithms Data mining Discrete geometry Geometric algorithms Mathematical optimization Search algorithms