An Algorithm for Finding Best Matches in Logarithmic Expected Time

10.1145/361002.361007

10.1145/362003.362025

FINKEL , R.A. , AND BENTLEY , J.L . Quad trees--a data structure for retrmval on composite keys . Acta Informatica 4 , 1 ( 1974 ), 1-9. FINKEL, R.A., AND BENTLEY, J.L. Quad trees--a data structure for retrmval on composite keys. Acta Informatica 4, 1 (1974), 1-9.

FRIEDMAN , J.H. , BASKETT , F. , AND SHUSTEK , L.J . An algorithm for finding nearest neighbors . IEEE Trans. Comptrs C-24 ( 1975 ), 1000 - 1006 . FRIEDMAN, J.H., BASKETT, F., AND SHUSTEK, L.J. An algorithm for finding nearest neighbors. IEEE Trans. Comptrs C-24 (1975), 1000-1006.

FUKUNAGA , K. , AND HOSTETLER , L.D Optimization of k-nearest neighbor density estimates. 1EEE Trans . Inform Theory IT-19 ( 1973 ), 320 - 326 . FUKUNAGA, K., AND HOSTETLER, L.D Optimization of k-nearest neighbor density estimates. 1EEE Trans. Inform Theory IT-19 (1973), 320-326.

FUKUNAGA , K. , AND NARENDRA , P.M . A branch and bound algorithm for computing k-nearest neighbors . IEEE Trans. Comptrs. C-24 ( 1975 ), 750 - 753 . FUKUNAGA, K., AND NARENDRA, P.M. A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. Comptrs. C-24 (1975), 750-753.

HYAYIL , L. , Am) RZVEST , R.L . Constructing optimal binary decision trees is NP-complete . Information Processing Letters 5 , ( May 1976 ), 15 - 17 . HYAYIL, L., Am) RZVEST, R.L. Constructing optimal binary decision trees is NP-complete. Information Processing Letters 5, (May 1976), 15-17.

KNUTH , D.E. The Art of Computer Programming , Vol. 1 , Addison-Wesley , Reading, Mass ., 1969 , p. 401. KNUTH, D.E. The Art of Computer Programming, Vol. 1, Addison-Wesley, Reading, Mass., 1969, p. 401.

PIZER , S.M. Numerical Computing and Mathematical Analysis , Science Research Associates , Chicago, Ill ., 1975 , p. 88, eq. 87. PIZER, S.M. Numerical Computing and Mathematical Analysis, Science Research Associates, Chicago, Ill., 1975, p. 88, eq. 87.

RIVEST , R. On the optimality of Elias' algorithm for performing best match searches. Information Processing 74 , North-Holland Pub. Co. , Amsterdam , 1974 , pp. 678 - 681 . RIVEST, R. On the optimality of Elias' algorithm for performing best match searches. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 678-681.

SHAMOS , M.I. Geometric Complexity. Conf. Rec. Seventh Annual ACM Syrup. on Theory of Comptng , Albuquerque, N.Mex. , May 1975 , 224 - 233 . 10.1145/800116.803772 SHAMOS, M.I. Geometric Complexity. Conf. Rec. Seventh Annual ACM Syrup. on Theory of Comptng, Albuquerque, N.Mex., May 1975, 224-233. 10.1145/800116.803772