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 kNNP in N + 2 rootN × K systolic steps using rootN × K processing elements, where N is the problem size (i.e., the number of points), and K is the sum of all k-values.
