Abstract
We 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. Our algorithm can solve a multiple-shot kNNP in N + 2 √N x K systolic steps using √ N x K processing elements, where N is the problem size (i.e., the number of points), and K is the sum of all k-values. © 1992 IEEE