Skip to main content
Cross Validated

Return to Question

Update: Found a paper describing a suitable algorithm
Source Link
Paul Chernoch
Paul Chernoch
  • 226
  • 2
  • 8

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.

UPDATE:

I found an utterly simple, reasonably accurate, low memory footprint algorithm for estimating quantiles which I can use in place of standard deviation. I was astonished when I read the paper.

For a layman's overview blog post which links to a cool interactive simulator, see http://research.neustar.biz/2013/09/16/sketch-of-the-day-frugal-streaming/

For the paper itself, see "Frugal Streaming for Estimating Quantiles: One (or two) memory suffices" by Qiang Ma, S. Muthukrishnan and Mark Sandler at this URL: http://arxiv.org/pdf/1407.1121v1.pdf

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.

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.

UPDATE:

I found an utterly simple, reasonably accurate, low memory footprint algorithm for estimating quantiles which I can use in place of standard deviation. I was astonished when I read the paper.

For a layman's overview blog post which links to a cool interactive simulator, see http://research.neustar.biz/2013/09/16/sketch-of-the-day-frugal-streaming/

For the paper itself, see "Frugal Streaming for Estimating Quantiles: One (or two) memory suffices" by Qiang Ma, S. Muthukrishnan and Mark Sandler at this URL: http://arxiv.org/pdf/1407.1121v1.pdf

Source Link
Paul Chernoch
Paul Chernoch
  • 226
  • 2
  • 8

How can I estimate the sliding window standard deviation of a stream?

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.