BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-482
       ENTRY:: June 10, 1998 
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: An Algroithm for Finding Best Matches in Logarithmic Expected Time
        TYPE:: Technical Report
      AUTHOR:: Friedman, Jerome
      AUTHOR:: Bentley, Jon Louis
      AUTHOR:: Finkel, Raphael Ari
        DATE:: July 1976
       PAGES:: 40 
    ABSTRACT:: An algorithm and data structure are presented for
searching a file containing N records, each described by k real
valued keys, for the m closest matches or nearest neighbors to
a given query record.  The computation required to organize the 
file is proportional to kNlogN.  The expected number of records
examined in each search is independent of the file size.  The
expected computation to perform each search is proportional to logN.
Empirical evidence suggests that except for very small files, this
algorithm is considerably faster than other methods.
         END:: STAN//CS-TR-75-482