Monroe, LauraWendelberger, JoanneMichalak, SarahCarsten Dachsbacher and William Mark and Jacopo Pantaleoni2016-02-182016-02-182011978-1-4503-0896-02079-8687https://doi.org/10.1145/2018323.2018338We implement here a fast and memory-sparing probabilistic top k selection algorithm on the GPU. The algorithm proceeds via an iterative probabilistic guess-and-check process on pivots for a three-way partition. When the guess is correct, the problem is reduced to selection on a much smaller set. This probabilistic algorithm always gives a correct result and always terminates. Las Vegas algorithms of this kind are a form of stochastic optimization and can be well suited to more general parallel processors with limited amounts of fast memory.D.1.3 [Concurrent Programming]Parallelprogramming. F.2.2 [Nonnumerical Algorithms andProblems]Nonnumerical Algorithms and Problems Sortingand searching. G.3 [Probability and Statistics]ProbabilisticAlgorithms. 1.3.1 [Computer Graphics]Hardware Architecture Graphics processors. 1.3.1 [Computer Graphics]HardwareArchitecture Parallel processing.Experimental parallel algorithmsGPGPULas Vegasalgorithmprobabilistic algorithmsselectionkth order statistic.10.1145/2018323.201833889-98