Report Number: CS-TR-89-1276
Institution: Stanford University, Department of Computer Science
Title: On the network complexity of selection
Author: Plaxton, C. Greg
Date: August 1989
Abstract: The selection problem is to determine the kth largest out of a given set of n keys, and its sequential complexity is well known to be linear. Thus, given a p processor parallel machine, it is natural to ask whether or not an O(n/p) selection algorithm can be devised for that machine. For the EREW PRAM, Vishkin has exhibited a straightforward selection algorithm that achieves optimal speedup for n = Omega(p log p log log p) [18]. For the network model, the sorting result of Leighton [12] and the token distribution result of Peleg and Upfal [13] together imply that Vishkin's algorithm can be adapted to run in the same asymptotic time bound on a certain class of bounded degree expander networks. On the other hand, none of the network families currently of practical interest have sufficient expansion to permit an efficient implementation of Vishkin's algorithm. The main result of this paper is an Omega((n/p) log log p + log p) lower bound for selection on any network that satisfies a particular low expansion property. The class of networks satisfying this property includes all of the common network families such as the tree, multi-dimensional mesh, hypercube, butterfly and shuffle exchange. When n/p is sufficiently large (for example, greater than log2 p on the butterfly, hypercube and shuffle exchange), this result is matched by the upper bound presented in [14].
http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1276/CS-TR-89-1276.pdf