Re: [boost] [Review] Review of the Accumulators library begins today Jan 29

From: Ben FrantzDale (benfrantzdale_at_[hidden])
Date: 2007-01-31 10:19:38

On 1/31/07, james.jones_at_[hidden] <james.jones_at_[hidden]>
wrote:
>
> From: Matthias Troyer <troyer_at_[hidden]>
> > These were easy, trickier are robust estimators of variance and
> > moments, even trickier will be median estimators where I currently
> > even do not see how this should be done without storing most of the
> > time series.
>
> Isn't this already a problem with sequences? Suppose you're storing the
> current median, and a new value comes along. What's the new median - without
> checking all the previous values? There are statistical estimates for this,
> but I don't know any exact way other than essentially resorting the data and
> checking the new median.

Good point. Combining partial results may not be possible for all
accumulated statistics or there may be a cost to making a statistic
"combinable". Perhaps a refinement of the Accumulator concept would be
needed.

The idea of the Accumulator library is to implement online algorithms; is
there a corresponding word for online algorithms for which partial results
can be combined?

—Ben

PS
For reference, these two pages may be of use:
http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Algorithm_III
http://en.wikipedia.org/wiki/Sum_of_normal_distributions