Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system

Yi Pan; Keqin Li; Si-Qing Zheng

doi:10.1109/ISPAN.1997.645135

Parallel Architectures, Algorithms, and Networks, International Symposium on

Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system

Year: 1997, Pages: 444

DOI Bookmark: 10.1109/ISPAN.1997.645135

Authors

Yi Pan, Dept. of Comput. Sci., Dayton Univ., OH, USA
Keqin Li, Dept. of Comput. Sci., Dayton Univ., OH, USA
Si-Qing Zheng, Dept. of Comput. Sci., Dayton Univ., OH, USA

Abstract

We present efficient algorithms for the nearest neighbor problem defined in an n/spl times/n binary image. We show that using a linear array with a reconfigurable pipelined bus system (LARPBS) of n/sup 2/ processors, the nearest neighbor problem can be solved in O(log log n) time, and using an LARPBS of n/sup 3/ processors, the nearest neighbor problem can be solved in O(1) time. We also show that the nearest neighbor problem can be solved on an LARPBS of n/sup 2/ processors in O(1) time with high probability.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!