Skip to Main content Skip to Navigation
Conference papers

Efficient Incremental Computation of Aggregations over Sliding Windows

Chao Zhang 1 Reza Akbarinia 2 Farouk Toumani 1
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03359490
Contributor : Reza Akbarinia Connect in order to contact the contributor
Submitted on : Thursday, September 30, 2021 - 11:26:22 AM
Last modification on : Friday, October 22, 2021 - 3:07:19 PM

File

PBA_KDD_21.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

26

Files downloads

71