© 1996 by British Computer Society
Parallel Threshold Voting
Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106-9560, USA. Email: parhami{at}ece.ucsb.edu
Voting on large collections of input objects is becoming increasingly important in data fusion, signal and image processing applications, learning algorithms, and distributed computing. To achieve high speed in voting, the multiple processing resources typically available in such applications should be utilized; hence the need for parallel voting algorithms. We develop efficient parallel algorithms for threshold voting which generalize and extend previous work on both sequential threshold voting and parallel majority voting. Our discussion centers on unweighted threshold (m-out-of-n) voting. However, we observe that under certain conditions, the results can be extended to efficient weighted threshold voting. We show how a known O(n)-time sequential algorithm for m-out-of-n voting can be parallelized through a simple divide-and-conquer strategy. When m = 
(n), the resulting algorithm has O(log2n) time complexity on n-processor PRAM and hypercubic computers and O(k2n1/k) time complexity on a k-dimensional mesh with n processors. We also analyse the time complexity of the algorithm for m = o(n) and its special case of m = (1).
Received August 14, 1995. revised June 28, 1996.
* Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106-9560, USA Email: parhami{at}ece.ucsb.edu