Title :
A systolic algorithm for the k-nearest neighbors problem
Author :
Chen, Yirng-An ; Lin, Youn-Long ; Chang, Long-Wen
Author_Institution :
Dept. of Comput. Sci., Tsing-Hua Univ., Hsin-Chu, Taiwan
fDate :
1/1/1992 12:00:00 AM
Abstract :
The authors present a systolic algorithm and its variations for the k-nearest neighbors problem (kNNP). Multiple-shot queries with different ranges (k values) can be served in a pipelined fashion. A partitioning scheme is developed to handle large size problems. Performance of the algorithm is analyzed. Formulas for the optimal array size in terms of computation time and area-time-time product (ATT) are derived. The algorithm can solve a multiple-shot k NNP in N+2√N×K systolic steps using √N×K processing elements, where N is the problem size (i.e. the number of points), and K is the sum of all k-values
Keywords :
computational geometry; systolic arrays; area-time-time product; computation time; k-nearest neighbors problem; multiple-shot queries; optimal array size; partitioning scheme; systolic algorithm; Algorithm design and analysis; Concurrent computing; Distributed computing; Geometry; Merging; Partitioning algorithms; Performance analysis; Sorting; Systolic arrays; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
