I wanted to share with you a clever algorithm that you might not know about for computing running averages over a large data set without having to store the invividual values in that set. The average is weighted so that more recent values have a stronger weight than older values. I'll leave it to others to decide if it would be useful in Auctioneer, but I think it might be.
The algorithm is based on a "radioactive decay" model. The weight of each value in the average decays over time based on a "half-life". If the half-life is set to one week, then values that are a week old have half the weight of new values. Values that are two weeks old have 1/4 the weight, etc. The weight of very old values never goes away entirely, but it becomes so small as to be negligible.
The algorithm only stores three numbers: the "total", the "count", and a timestamp. As usual, the average is computed by dividing the total by the count. What is unusual about the algorithm is how the total and the count are updated when new values are accumulated in the average.
Before recording a new value, the "total" and "count" are adjusted to account for the decay that has taken place between the stored timestamp and the timestamp on the new value. Assuming that t1 is the old timestamp, t2 is the new timestamp, and hl is the half-life, the decay factor is:
decay = 1 / (2 ^ ((t2 - t1) / hl))
Both the total and the count are multiplied by the decay factor, and the stored timestamp is updated to the timestamp of the new value. Now that the timestamps match, the new value can be recorded simply by adding the new value to the total, and adding 1 to the count.
I hope my explanation is clear. I know that Auctioneer has to store a history of values in order to compute medians and such, so there may not be any advantage to this algorithm. Still, I thought it was worth talking about.