Efficient Incremental Computation of Aggregations over Sliding Windows - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2021

Efficient Incremental Computation of Aggregations over Sliding Windows

Résumé

Computing aggregation over sliding windows, i.e., finite subsets of an unbounded stream, is a core operation in streaming analytics. We propose PBA (Parallel Boundary Aggregator), a novel parallel algorithm that groups continuous slices of streaming values into chunks and exploits two buffers, cumulative slice aggregations and left cumulative slice aggregations, to compute sliding window aggregations efficiently. PBA runs in (1) time, performing at most 3 merging operations per slide while consuming () space for windows with partial aggregations. Our empirical experiments demonstrate that PBA can improve throughput up to 4× while reducing latency, compared to state-of-the-art algorithms.
Fichier principal
Vignette du fichier
PBA_KDD_21.pdf (2.5 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03359490 , version 1 (30-09-2021)

Identifiants

Citer

Chao Zhang, Reza Akbarinia, Farouk Toumani. Efficient Incremental Computation of Aggregations over Sliding Windows. KDD 2021 - 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Aug 2021, Singapore (Virtual), Singapore. pp.2136-2144, ⟨10.1145/3447548.3467360⟩. ⟨lirmm-03359490⟩
109 Consultations
650 Téléchargements

Altmetric

Partager

More