Computing Time-Decayed Aggregates in Data Streams

An apparatus comprising:

• a processor;
• and
• a memory to store computer program instructions for calculating a time-decayed aggregate from a data stream comprising a sequence of tuples, each tuple comprising an item identifier and an associated timestamp, the computer program instructions when executed on the processor cause the processor to perform operations comprising:
• generating a time-dependent weighted sequence of tuples by multiplying each of the sequence of tuples by a time-dependent weighting factor calculated from a decay function, wherein the decay function is a function of the timestamp associated with the tuple and a current time;
• generating a quantile-digest data structure from the time-dependent weighted sequence of tuples;
• updating the quantile-digest data structure with the time-dependent weighted sequence of tuples;
• and,
• calculating the time-decayed aggregate from the updated quantile-digest data structure.