A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution

Thumbnail Image
Full text at PDC
Publication Date
Advisors (or tutors)
Journal Title
Journal ISSN
Volume Title
Elsevier Science Inc
Google Scholar
Research Projects
Organizational Units
Journal Issue
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.
We are indebted to the unknown referees for enlightening observations, which helped us to improve the paper. The authors would also like to thank G. Cormode and M. Hadjieleftheriou for making freely available their sequential implementation of the Space Saving algorithm. We are also grateful to Prof. Palpanas of Paris Descartes University for providing us with the real datasets used in the experiments. The research of M. Cafaro has been supported by CMCC, Italy, under the grant FISR Gemina project, Italian Ministry of Education, University and Research. The research of P. Tempesta has been supported by the grant FIS2011–22566, Ministerio de Ciencia e Innovaci´on, Spain.
Unesco subjects