Publication: In-order sliding-window aggregation in worst-case constant time
Issued Date
2021-11-01
Resource Type
ISSN
0949877X
10668888
10668888
Other identifier(s)
2-s2.0-85107414145
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
VLDB Journal. Vol.30, No.6 (2021), 933-957
Suggested Citation
Kanat Tangwongsan, Martin Hirzel, Scott Schneider In-order sliding-window aggregation in worst-case constant time. VLDB Journal. Vol.30, No.6 (2021), 933-957. doi:10.1007/s00778-021-00668-3 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/76631
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
In-order sliding-window aggregation in worst-case constant time
Author(s)
Other Contributor(s)
Abstract
Sliding-window aggregation is a widely-used approach for extracting insights from the most recent portion of a data stream. While aggregations of interest can usually be expressed as binary operators that are associative, they are not necessarily commutative nor invertible. Non-invertible operators, however, are difficult to support efficiently. DABA is the first algorithm for sliding-window aggregation with worst-case constant time. Prior to DABA, the best published algorithms would require O(log n) aggregation steps per window operation for a window of size n—and while for strictly in-order streams, this bound could be improved to O(1) aggregation steps in the amortized sense, it was not known how to achieve an O(1) bound in the worst case, which is critical for latency-sensitive applications. In this article, besides describing DABA in more detail, we introduce a new variant, DABA Lite, which achieves the same time bounds in less memory. Whereas DABA requires space for storing 2n partial aggregates, DABA Lite only requires space for n+ 2 partial aggregates. Our experiments on synthetic and real data support the theoretical findings.