RT Journal Article
T1 A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution
A1 Cafaro, Massimo
A1 Pulimeno, Marco
A1 Tempesta, Piergiulio
AB 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.
PB Elsevier  Science Inc
SN 0020-0255
YR 2016
FD 2016-02-01
LK https://hdl.handle.net/20.500.14352/23153
UL https://hdl.handle.net/20.500.14352/23153
LA eng
NO 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.
NO Ministerio de Ciencia e Innovación (MICINN)
NO CMCC, Italy, under the grant FISR Gemina project
NO Italian Ministry of Education, University and Research
DS Docta Complutense
RD 6 abr 2025