Maintaining Wavelet Synopses for Sliding-Window Aggregates

The IoT era has brought forth a computing paradigm shift from traditional high-end servers to "edge" devices of limited processing and memory capabilities. These devices, together with sensors, regularly produce very high data volumes nowadays. For many real-time applications, storing and indexing an unbounded stream may not be an option. Thus, it is important that we design algorithms and systems that can both work at the edge of the network and be able to answer queries on distributed, streaming data. Moreover, in many streaming scenarios, fresh data tend to be prioritized. A sliding-window model is an important case of stream processing, where only the most recent elements remain active and the rest are discarded. In this work, we study the problem of maintaining basic aggregate statistics over a sliding-window data stream under the constraint of limited memory. As in IoT scenarios the available memory is typically much less than the window size, queries are answered from compact synopses that are maintained in an online fashion. For the efficient construction of such synopses, in this work, we propose wavelet-based algorithms that provide deterministic guarantees and produce almost exact results. Our algorithms can work on any kind of numerical data and do not have the positive-numbers constraint of techniques such as the exponential histograms. Our experimental evaluation indicates that, in terms of accuracy and space-efficiency, our solution outperforms the exponential histograms and deterministic waves techniques.