Parallel algorithms for m-out-of-n threshold voting
Behrooz Parhami · 2002
Voting on large collections of input objects is becoming increasingly important in data fusion, signal and image processing, 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. We show how a well-known O(n)-time sequential algorithm for m-out-of-n voting can be parallelized through 1 simple divide-and-conquer strategy. When m=/spl theta/(n), the resulting algorithm has O(log/sup 2/ n) time complexity on PRAM and hypercube computers and optimal O(n/sup 1/k/) complexity on a k-dimensional mesh-connected architecture. We also analyze the time complexity of the algorithm in the case of m=o(n) and for certain weighted threshold voting schemes.