Title :
Complexity analysis for partitioning nearest neighbor searching algorithms
Author :
Zakarauskas, Pierre ; Ozard, John M.
Author_Institution :
Dept. of Ophthalmology, British Columbia Univ., Vancouver, BC, Canada
fDate :
6/1/1996 12:00:00 AM
Abstract :
Presents cost estimates for finding the k-nearest neighbors to a test pattern according to a Minkowski p-metric, as a function of the size of the buckets in partitioning searching algorithms. The asymptotic expected number of operations to find the nearest neighbor is presented as a function of the average number of patterns per bucket n and is shown to contain a global minimum
Keywords :
computational complexity; pattern classification; search problems; Minkowski p-metric; complexity analysis; cost estimates; global minimum; nearest neighbor searching algorithms; partitioning; Algorithm design and analysis; Cost function; Distribution functions; Nearest neighbor searches; Neural networks; Partitioning algorithms; Pattern analysis; Pattern recognition; Search methods; Testing;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
