Sliding Window Computations over Data Streams
Brian Babcock, Mayur Datar, Rajeev Motwani, Liadan O'Callaghan · 2002
We extend the work from our earlier paper (SODA 2002), to maintain complex statistics in the sliding window model that cannot be estimated using previous techniques. In particular we consider the following two problems and provide solutions to them that require very less memory: estimating the variance and maintaining the cluster centers (k-medians).