On Demand Introductory Videos
Download Now Instant Evaluation
Get Price Quote
  • Home
  • Resources
  • Papers
  • "AN ALGORITHM FOR FINDING BEST MATCHES IN LOGARITHMIC EXPECTED TIME" - Jerome H. Friedman

"AN ALGORITHM FOR FINDING BEST MATCHES IN LOGARITHMIC EXPECTED TIME" - Jerome H. Friedman

Jerome Friedman Jerome H. Friedman
Stanford Linear Accelerator Center
Stanford University, Stanford, Ca. 94305

Jon Louis Bentley
Department of Computer Science
University of North Carolina at Chapel Hill
Chapel Hill, N.C. 27514

Raphael Ari Finkel
Department of Computer Science
Stanford University, Stanford, Ca. 94305

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 1ogN. Empirical evidence suggests that except for very small files, this algorithm is considerably faster than other methods.

Tags: papers, Jerome Friedman, Salford-Systems

Get In Touch With Us

Contact Us

9685 Via Excelencia, Suite 208, San Diego, CA 92126
Ph: 619-543-8880
Fax: 619-543-8888
info (at) salford-systems (dot) com