A Parallel Space Saving Algorithm and Performance Test
Siyuan Chang, Jun Liu, Fang Liu, Jie Yang · 2016
Finding k-majority elements in a data set is becoming increasingly critical in a lot of applications. These algorithms are generally classified as the counter-based and the sketch-based, and both types try to deliver high throughput with limited resources. Space Saving, which exhibits desirable efficiency and accuracy among counter-based algorithms, could meet our requirements in most cases. In this paper, we present an message-passing algorithm to solve the k-majority problem, which named parallel space saving algorithm. We not only present the basic theories of this algorithm and explain how the algorithm is parallelized, but also show the experimental results of it. Some suggestions are given to improve the performance and reduce the running time of this algorithm in a practical situation.