Smooth Histograms for Sliding Windows.
Vladimir Braverman, Rafail Ostrovsky
Abstract:
In the streaming model, elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and non-trivial task in the model. This becomes even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar, Gionis, Indyk and Motwani presented exponential histograms, an effective method for estimating statistics on sliding windows. In this paper we present a new smooth histograms method that improves the approximation error rate obtained via exponential histograms. Furthermore, our smooth histograms method not only captures and improves multiple previous results on sliding windows but also extends the class functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: Lp norms for p other than [1; 2], frequency moments, length of increasing subsequence and geometric mean.
comment: FOCS 2007: 283-293
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |