2019/01/02 by Nikolaus Binder, Alexander Keller, Binder, Nikolaus +1
Computer Science · #Anomaly Detection Techniques and Applications #Data Management and Algorithms #Distributed #FOS: Computer and information sciences #Graphics (cs.GR) #Parallel #Time Series Analysis and Forecasting #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1901.05423
openalex publication_date 2019/01/02 · openalex created_date 2019/01/25 · openalex updated_date 2026/07/28
We compare different methods for sampling from discrete probability distributions and introduce a new algorithm which is especially efficient on massively parallel processors, such as GPUs. The scheme preserves the distribution properties of the input sequence, exposes constant time complexity on the average, and significantly lowers the average number of operations for certain distributions when sampling is performed in a parallel algorithm that requires synchronization afterwards. Avoiding load balancing issues of naïve approaches, a very efficient massively parallel construction algorithm for the required auxiliary data structure is complemented.