Title :
Sorting-based selection algorithms for hypercubic networks
Author :
Berthome, P. ; Ferreira, Andre ; Maggs, B.M. ; Perennes, S. ; Plaxton, C.G.
Author_Institution :
Lab. de Inf. du Parallelisme, Ecole Normale Superieure de Lyon, France
Abstract :
This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap (1985), as well as on various sorting algorithms for hypercubic networks. The authors fastest algorithm runs in O(lg n lg*n) time, very nearly matching the trivial Ω(lg n) lower bound. Previously, the best upper bound known for selection was O(lg n lg lg n)
Keywords :
hypercube networks; sorting; deterministic algorithms; hypercubic networks; kth largest record; sorting based selection algorithms; upper bound; Algorithms; Hypercubes; Joining processes; Parallel processing; Partial response channels; Radio access networks; Sampling methods; Sorting; Statistics; Upper bound;
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
DOI :
10.1109/IPPS.1993.262861
