Publication: Low-latency sliding-window aggregation in worst-case constant time
Issued Date
2017-06-08
Resource Type
Other identifier(s)
2-s2.0-85023175463
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
DEBS 2017 - Proceedings of the 11th ACM International Conference on Distributed Event-Based Systems. (2017), 66-77
Suggested Citation
Kanat Tangwongsan, Martin Hirzel, Scott Schneider Low-latency sliding-window aggregation in worst-case constant time. DEBS 2017 - Proceedings of the 11th ACM International Conference on Distributed Event-Based Systems. (2017), 66-77. doi:10.1145/3093742.3093925 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/42439
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Low-latency sliding-window aggregation in worst-case constant time
Author(s)
Other Contributor(s)
Abstract
© 2017 ACM. Sliding-window aggregation is a widely-used approach for extracting insights from the most recent portion of a data stream. The aggregations of interest can usually be cast as binary operators that are associative, but they are not necessarily commutative nor in-vertible. Non-invertible operators, however, are difficult to support efficiently. The best published algorithms require O(log n) aggregation steps per window operation, where n is the sliding-window size at that point. For a FIFO window, this can be improved to 0(1) on average by using two aggregation stacks. This paper presents DABA, a novel algorithm for aggregating FIFO sliding windows that significantly improves upon these time bounds. DABA requires only 0(1) aggregation steps per operation in the worst case (not just on average). As such, DABA asymptotically improves the performance of sliding-window aggregation without restricting the operator to be invertible. Our experimental results demonstrate that these theoretical improvements hold in practice. DABA is a substantial improvement over the state of the art in terms of both latency and throughput.
