Abstract

We present a deterministic parallel algorithm for the k-majority problem, that can be used to find in parallel frequent items, i.e. those whose multiplicity is greater than a given threshold, and is therefore useful to process iceberg queries and in many other different contexts of applied mathematics and information theory. The algorithm can be used both in the online (stream) context and in the offline setting, the difference being that in the former case we are restricted to a single scan of the input elements, so that verifying the frequent items that have been determined is not allowed (e.g. network traffic streams passing through internet routers), while in the latter a parallel scan of the input can be used to determine the actual k-majority elements. To the best of our knowledge, this is the first parallel algorithm solving the proposed problem.

Autore Pugliese

• Cafaro Massimo

Tutti gli autori

• M. Cafaro , P. Tempesta

Titolo volume/Rivista

CONCURRENCY AND COMPUTATION

Anno di pubblicazione

2011

ISSN

1532-0626

ISBN

Non Disponibile

Numero di citazioni Wos

14

Ultimo Aggiornamento Citazioni

28/04/2018

Numero di citazioni Scopus

18

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile