algorithm to update an aggregated value when an element changes

Question

(I'm using C# but this isn't necessarily platform-specific)

Say I have a table of values, which are indexed by a triplet of keys (A, B, C). The values in the table are streaming in from an outside source at sporadic intervals. I want to publish aggregates over various sets of keys, e.g. calculate a sum over all values where B = b1.

This is trivial to do if I just iterate over the entire table each time, but obviously that's not efficient. What I'm wondering is, is there a particularly good way to design such a thing so that I only update sum(B = b1) when a value in the table changes that would affect this sum? It seems like I would need to create some sort of Aggregation object that maintains a list of every value that is included in that aggregation, but I feel like there might be a more elegant way that's escaping me. Something like a "real time" LINQ query...

Answer 1

Well, for the simple example that you presented, why not have an event, say, OnValueChanging that signals the value that is about to change? Then you can record the current value, say, x. Then fire another event OnValueChanged and record the new value, say, y. Then the sum that you want to update is currentSum - x + y.

Answer 2

Use a Dictionary<TypeOfB, int>. Everytime you add a new b, do

dictionary[b] += value;

If a value changes, do

dictionary[b] += (newValue - oldValue)