Finding Top-k Most Frequent Items in Distributed Streams in the Time-Sliding Window Model

Emmanuelle Anceaume (1) , Yann Busnel (2, 3, 4) , Vasile Cazacu (1)

1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
2 IMT Atlantique - IMT Atlantique
3 IMT Atlantique - SRCD - Département Systèmes Réseaux, Cybersécurité et Droit du numérique
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS

We propose a new probabilistic algorithm to find the top-k most recent and frequent items in distributed streams. This algorithm significantly improves upon the reliability and accuracy of existing results, while significantly reducing the memory footprint needed by each of the distributed nodes to solve this problem.

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Théorie de l'information [cs.IT]

Emmanuelle Anceaume, Yann Busnel, Vasile Cazacu. Finding Top-k Most Frequent Items in Distributed Streams in the Time-Sliding Window Model. DSN 2018 - 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Jun 2018, Luxembourg, Luxembourg. pp.1-2, ⟨10.1109/DSN-W.2018.00030⟩. ⟨hal-01839930⟩