Probably correct k-nearest neighbor search in high dimensions

Cover, 1967, Nearest neighbor pattern classification, IEEE Transactions on Information Theory, IT-13, 21, 10.1109/TIT.1967.1053964

Chang, 1993, A hashing-oriented nearest neighbor searching scheme, Pattern Recognition Letters, 14, 625, 10.1016/0167-8655(93)90047-H

Dasarathy, 1994, Minimal consistent set (MCS) identification for optimal neighbor decision systems design, IEEE Transactions on Systems, Man, & Cybernetics, SMC-24, 511, 10.1109/21.278999

Fukunaga, 1975, A branch-and-bound algorithm for computing k-nearest neighbors, IEEE Transactions on Computers, C-24, 750, 10.1109/T-C.1975.224297

J.H. Friedman, F. Naskett, L.J. Shustek, An algorithm for finding nearest neighbors, IEEE Transactions on Computers, October (1975) 1000–1006.

Friedman, 1977, An algorithm for finding best matches in logarithm expected time, ACM Transactions on Mathematical Software, 3, 209, 10.1145/355744.355745

Gates, 1972, The reduced nearest neighbor rule, IEEE Transactions on Information Theory, IT-18, 431, 10.1109/TIT.1972.1054809

Hart, 1968, The condensed nearest neighbor rule, IEEE Transactions on Information Theory, IT-14, 515, 10.1109/TIT.1968.1054155

A. Califano, R. Mohan, Multidimensional indexing for recognizing visual shapes, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 1991, pp. 28–34.

H.J. Wolfson, Model-based object recognition by geometric hashing, in: Proceedings of the 1st European Conference on Computer Vision, April 1990, pp. 526–536.

Bentley, 1975, Multidimensional binary search trees used for associative searching, Communications of the ACM, 18, 509, 10.1145/361002.361007

Bentley, 1980, Optimal expected-time algorithms for closest-point problems, ACM Transactions on Mathematical Software, 6, 563, 10.1145/355921.355927

A. Guttman, R-trees: a dynamic index structure for spatial searching, in: ACM SIGMOD, June 1984, pp. 47–57.

T. Sellis, N. Roussopoulos, C. Faloutos, The R+- tree: a dynamic index for multi-dimensional objects, in: Proceedings of the 13th VLDB Conference, 1987, pp. 507–517.

S. Berchtold, D.A. Keim, H.-P. Kriegel, The X-tree: an index structure for high-dimensional data, in: Proceedings of the 22nd VLDB Conference, 1996, pp. 28–39.

Djouadi, 1997, A fast algorithm for the nearest-neighbor classifier, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 277, 10.1109/34.584107

S. Berchtold, B. Ertl, D.A. Keim, H.-P. Kriegel, T. Seidl, Fast nearest neighbor search in high-dimensional spaces, in: Proceedings of the 14th IEEE Conference on Data Engineering, ICDE, 1998, pp. 23–27.

Nene, 1997, A simple algorithm for nearest neighbor search in high dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 989, 10.1109/34.615448

D.Y. Cheng, et al., Fast search algorithms for vector quantization and pattern matching, in: Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, 1984, pp. 372–375.

McNames, 2001, A fast nearest-neighbor algorithm based on a principal axis search tree, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 964, 10.1109/34.955110

Arya, 1998, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM, 45, 891, 10.1145/293347.293348

J.M. Kleinberg, Two algorithms for nearest-neighbor search in high dimension, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 599–608.

Maneewongvatana, 2001, An empirical study of a new approach to nearest neighbor searching, vol. 2513, 172

P. Ciaccia, M. Patella, PAC nearest neighbor queries: approximate and controlled search in high-dimensional and metric spaces, in: Proceedings of the 16th International Conference on Data Engineering, 2000, pp. 244–255.

P. Indyk, R. Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.

Andoni, 2006, Locality-sensitive hashing using stable distributions

Andoni, 2008, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, 51, 117, 10.1145/1327452.1327494

Fukunaga, 1990

Y.Le. Cunn, The MNIST dataset of handwritten digits, Available at: 〈http://yann.lecun.com/exdb/mnist/〉.

Baccini, 1996, A L1-norm PCA and a heuristic approach, 359

Kwak, 2008, Principal component analysis based on L1-norm maximization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 1672, 10.1109/TPAMI.2008.114