Given an array @math of @math elements and a value @math , a frequent item or @math -majority element is an element occurring in @math more than @math times. The @math -majority problem requires finding all of the @math -majority elements. In this paper we deal with parallel shared-memory algorithms for frequent items; we present a shared-memory version of the Space Saving algorithm and we study its behavior with regard to accuracy and performance on many and multi-core processors, including the Intel Phi accelerator. We also investigate a hybrid MPI OpenMP version against a pure MPI based version. Through extensive experimental results we prove that the MPI OpenMP parallel version of the algorithm significantly enhances the performance of the earlier pure MPI version of the same algorithm. Results also prove that for this algorithm the Intel Phi accelerator does not introduce any improvement with respect to the Xeon octa-core processor.
We design a parallel algorithm for frequent items based on the sequential Space Saving algorithm.We show that the algorithm is cost-optimal for k = O ( 1 ) and therefore extremely fast and useful in a wide range of applications.We experimentally validate the algorithm on synthetic data distributed using a Hurwitz zeta function and a Zipf one, and also on real datasets, confirming the theoretical cost-optimality and that the error committed is very low and close to zero.We compare the performances and the error committed by our algorithm against a parallel algorithm recently proposed by Agarwal et?al. for merging datasets derived by the Space Saving or Frequent algorithms. We present a message-passing based parallel version of the Space Saving algorithm designed to solve the k-majority problem. The algorithm determines in parallel frequent items, i.e., those whose frequency is greater than a given threshold, and is therefore useful for iceberg queries and many other different contexts. We apply our algorithm to the detection of frequent items in both real and synthetic datasets whose probability distribution functions are a Hurwitz and a Zipf distribution respectively. Also, we compare its parallel performances and accuracy against a parallel algorithm recently proposed for merging summaries derived by the Space Saving or Frequent algorithms.