I am processing a stream of database records. At current levels, about 250 million records are added per week, but this will increase. I wish to compute the 90-day sliding window standard deviation of values taken from these records. I may later decide that I need multiple windows of different lengths if I need to track seasonality, so 365-day windows are also a possibility.

The traditional approach is to store one full windows' worth of data. As data drops off the end, its contribution is subtracted. As new values are added, their contribution is added. I am acquainted with **Welford's method** as described in Knuth (*Art of Computer Programming*, Vol 2, page 232, 3rd edition) which guards against the catastrophic loss of precision found in the obvious algorithm.

However, storing the entire history is expensive. I wish to use an approximate algorithm that uses less memory/table space to maintain a sketch of the data from which an estimate may be derived.

I have already found suitable sketches for Max and Min by adapting the PartitionGreedy algorithm from the paper "**Competitive analysis of aggregate max in windowed streaming**" by Luca Becchetti and Elias Koutsoupias. I am using exponential smoothing with a suitable alpha value keyed to my window length to estimate the Mean and a similar technique for the Sum. Nevertheless, the standard deviation eludes me.

I have studied Count-Min Sketch and its generalization to windowed problems called ECM Sketch ("**Sketch-based Querying of Distributed Sliding-Window Data Streams**" by Papapetrou, Garofalakis and Deligiannakis), but they seem like overkill and are very complicated for this bear of little brain.

I also tried the range heuristics of **SD = (Max-Min) / 4** or **SD = (Max-Min) / 6** but the accuracy was horrible. Anything that is reasonably accurate (±5% would be great, ±10% would be tolerable) would be appreciated.