Abstract

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.

Autore Pugliese

• Cafaro Massimo

Tutti gli autori

• M. Cafaro , M. Pulimeno , P. Tempesta

Titolo volume/Rivista

INFORMATION SCIENCES

Anno di pubblicazione

2016

ISSN

0020-0255

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

7

Ultimo Aggiornamento Citazioni

24/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile