Cumulative sum of overlapping increase/decrease over time

Question

I am looking for an efficient way to handle a calculation. I have lots of timestamped events, representing loading and unloading of trucks. I need to construct the filling rate of these trucks over time.

This picture represents data and the wanted result. Keep in mind that the dataset is quite huge, and lots of events can overlap, even starting and/or ending at the same time.

Sometimes, loading is not known, so we must assume the truck is full (value=13).

I'm looking ideally for an agnostic algorithm or method.

Thanks a lot for your help

Answer 1

Data

The only pieces of information you need to know is the timestamp for every loading/unloading and the fill rate for each (for an unload event, fill rate will be negative to offset loading event).

Order all your data by this timestamp with its fill rate. Your current sum is current running total after you've added all these fill rates.

Tricks! - Running sum

Admittedly, for big sets of data like yours, this may take some time to calculate, but fear not! There are tricks!

Once you have the current running sum, save the current timestamp! This is important. The next time you need to determine the running sum, use the current running sum, and apply all load/unload events which happened after that timestamp. In this way you're sure to include all events.

If we want to be precise, you should create the timestamp prior to querying the data, and then you only grab data less recent than that timestamp (so you don't risk that new events are added after you've queried the data which don't get taken into consideration).

Tricks! - Reorganization

If querying data takes a long time to do, then you should reorganize your data in such a way that events which haven't yet been considered in the running sum are easily accessible. If you're using a database, this might mean putting it in its own table or partitioning the existing table by date.

If you're having difficulty converting the data to load/unload event timestamp and fill rate, then don't be afraid to reorganize the data as you see fit. You can do this using views if you're using a database, or you can simply reindex your data in memory before you order the data.

Conclusion

Let me know if that helps! If not, ask in the comments and I'll try to answer any questions you may have by updating my answer.

Answer 2

Create two lists. Both have items with have timestamp, value and 'kind'.

First list is created from beginning of events, value of that event and start kind. Second is created from end of event, value of that event and end 'kind'. Merge the two lists and order by timestamp.

Then enumerate the final list, adding value to accumulator when item is start kind and removing value when end kind.