variance estimation over sliding windows
Capturing characteristics of large data streams has received considerable attention. The constraints in space and time restrict the data stream processing to only one pass (or a small number of passes). Processing data streams over sliding windows make the problem more difficult and challenging. In this paper, we address the problem of maintaining ?-approximate variance of data streams over sliding windows. To our knowledge, the best existing algorithm requires O (1/?2 log N ) space, though the lower bound for this problem is ?(1/? log N ). We propose the first ?-approximation algorithm to this problem that is optimal in both space and worst case time. Our algorithm requires O (1/? log N ) space. Furthermore, its running time is O (1) in worst case.
variance estimation sliding windows data streams data mining