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 |
Year | DOI | Venue |
---|---|---|
1992 | 10.1109/12.123385 | IEEE Trans. Computers |
Keywords | Field | DocType |
k systolic step,area-time-time product,multiple-shot knnp,multiple-shot queries,square root,computational geometry,multiple-shot query,large size problem,computation time,problem size,systolic algorithm,systolic arrays,k processing element,k-nearest neighbors problem,partitioning scheme,optimal array size,concurrent computing,sorting,parallel processing,very large scale integration,algorithm design and analysis,k nearest neighbor,merging,geometry,distributed computing,computer architecture | k-nearest neighbors algorithm,Combinatorics,Nearest neighbour,Partition function (statistical mechanics),Computer science,Parallel processing,Computational geometry,Parallel computing,Algorithm,Multiprocessing,Square root,Computation | Journal |
Volume | Issue | ISSN |
41 | 1 | 0018-9340 |
Citations | PageRank | References |
5 | 1.08 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yirng-an Chen | 1 | 304 | 23.80 |
Youn-Long Lin | 2 | 748 | 71.39 |
Long-Wen Chang | 3 | 532 | 51.82 |