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.
The @math -majority problem has been solved sequentially first by Misra and Gries @cite_23 . @cite_18 and @cite_11 proposed independently optimal algorithms which, however, are identical to the Misra and Gries algorithm. , the algorithm designed by exploits better data structures (a doubly linked list of groups, supporting decrementing a set of counters at once in @math time) and achieves a worst-case complexity of @math . The algorithm devised by is based on hashing and therefore achieves the @math bound on average.
@cite_18 @cite_23 @cite_11
2597765082 2113139394
We consider a router on the Internet analyzing the statistical properties of a TCP IP packet stream. A fundamental difficulty with measuring traffic behavior on the Internet is that there is simply too much data to be recorded for later analysis, on the order of gigabytes a second. As a result, network routers can collect only relatively few statistics about the data. The central problem addressed here is to use the limited memory of routers to determine essential features of the network traffic stream. A particularly difficult and representative subproblem is to determine the top k categories to which the most packets belong, for a desired value of k and for a given notion of categorization such as the destination IP address. We present an algorithm that deterministically finds (in particular) all categories having a frequency above 1 (m+1) using m counters, which we prove is best possible in the worst case. We also present a sampling-based algorithm for the case that packet categories follow an arbitrary distribution, but their order over time is permuted uniformly at random. Under this model, our algorithm identifies flows above a frequency threshold of roughly 1 √nm with high probability, where m is the number of counters and n is the number of packets observed. This guarantee is not far off from the ideal of identifying all flows (probability 1 n), and we prove that it is best possible up to a logarithmic factor. We show that the algorithm ranks the identified flows according to frequency within any desired constant factor of accuracy. We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1 θ. The first pass is an on-line algorithm, generalizing a well-known algorithm for finding a majority element, for identifying a set of at most 1 θ items that includes, possibly among others, all items with frequency greater than θ.