Computing time-decayed aggregates under smooth decay functions
Aggregates are calculated from a data stream in which data is sent in a sequence of tuples, in which each tuple comprises an item identifier and a timestamp indicating when the tuple was transmitted. The tuples may arrive at a data receiver out-of-order, that is, the sequence in which the tuples arrive are not necessarily in the same sequence as their corresponding timestamps. In calculating aggregates, more recent data may be given more weight by a decay function which is a function of the timestamp associated with the tuple and the current time. The statistical characteristics of the tuples are summarized by a set of linear data summaries. The set of linear data summaries are generated such that only a single linear data summary falls between a set of boundaries calculated from the decay function and a set of timestamps. Aggregates are calculated from the set of linear data summaries.
1. A method 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, comprising the steps of:
generating a smooth decay function wherein said smooth decay function is a function of the difference between a current time and the timestamps;
generating a set of linear data summaries, based at least in part on a first set of timestamps;
generating a set of boundaries, based at least in part on the smooth decay function and on a second set of timestamps;
adding, with a data processor, each tuple to a specific linear data summary based at least in part on the timestamp associated with the tuple;
merging two linear data summaries based at least in part on the set of boundaries; and,
calculating, with the data processor, said aggregate from the set of linear data summaries.
2. The method of claim 1 ,
wherein the sequence of tuples is represented by the set {<x i , t i >} wherein x i , is the item identifier of the i-th tuple, t i is the timestamp associated with the i-th tuple, and i is a sequential integer index of the i-th tuple;
wherein the decay function is represented by the function g(t−t i ) wherein t is the current time;
wherein the set of linear data summaries is represented by the set {s i } wherein linear data summary s j summarizes the statistical characteristics of tuples with associated timestamps t i , in the range t j <t i <t j+1 ;
wherein the set of boundaries b i , is generated by the relationship g(b i )=(1+θ) −i where θ is an accuracy parameter; and,
wherein two linear data summaries are merged if the following relationship is true: (t−b i )<t j+2 <t j <(t−b i+1 ).
3. The method of claim 1 wherein the set of linear data summaries is a quantile-digest data structure.
4. The method of claim 1 further comprising the step of compressing the set of linear data summaries.
5. The method of claim 1 wherein said decay function is a polynomial decay function.
6. The method of claim 1 wherein said time-decayed aggregate is a time-decayed user-defined aggregate function.
7. The method of claim 1 wherein said time-decayed aggregate is a time-decayed count.
8. The method of claim 1 wherein said time-decayed aggregate is a time-decayed range.
9. The method of claim 1 wherein said time-decayed aggregate is a time-decayed quantile.
10. The method of claim 1 wherein said time-decayed aggregate is a time-decayed heavy hitter.
11. An apparatus 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, comprising the steps of:
means for generating a smooth decay function wherein said smooth decay function is a function of the difference between a current time and the timestamps;
means for generating a set of linear data summaries, based at least in part on a first set of timestamps;
means for generating a set of boundaries, based at least in part on the smooth decay function and on a second set of timestamps;
means for adding each tuple to a specific linear data summary based at least in part on the timestamp associated with the tuple;
means for merging two linear data summaries based at least in part on the set of boundaries; and, means for calculating said aggregate from the set of linear data summaries.
12. The apparatus of claim 11 , further comprising means for generating a quantile-digest data structure.
13. The apparatus of claim 11 , further comprising means for compressing the set of linear data summaries.
14. The apparatus of claim 11 , further comprising means for calculating a time-decayed user-defined aggregate function.
15. The apparatus of claim 11 , further comprising means for calculating a time-decayed count.
16. The apparatus of claim 11 , further comprising means for calculating a time-decayed range.
17. The apparatus of claim 11 , further comprising means for calculating a time-decayed quantile.
18. The apparatus of claim 11 , further comprising means for calculating a heavy hitter.
19. A non-transitory computer readable medium storing 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 defining the steps of:
generating a smooth decay function wherein said smooth decay function is a function of the difference between a current time and the timestamps;
generating a set of linear data summaries, based at least in part on a first set of timestamps;
generating a set of boundaries, based at least in part on the smooth decay function and on a second set of timestamps;
adding each tuple to a specific linear data summary based at least in part on the timestamp associated with the tuple;
merging two linear data summaries based at least in part on the set of boundaries; and,
calculating said aggregate from the set of linear data summaries.
20. The non-transitory computer readable medium of claim 19 wherein said computer program instructions defining the step of generating a set of linear data summaries further comprise computer program instructions defining the step of:
generating a quantile-digest data structure.
21. The non-transitory computer readable medium of claim 19 wherein said computer program instructions further comprise computer program instructions defining the step of:
compressing the set of linear data summaries.
22. The non-transitory computer readable medium of claim 19 wherein said computer program instructions defining the step of calculating a time-decayed aggregate further comprise computer instructions defining the step of:
calculating a time-decayed user-defined aggregate function.
23. The non-transitory computer readable medium of claim 19 wherein said computer program instructions defining the step of calculating a time-decayed aggregate further comprise computer instructions defining the step of:
calculating a time-decayed range.
24. The non-transitory computer readable medium of claim 19 wherein said computer program instructions defining the step of calculating a time-decayed aggregate further comprise computer instructions defining the step of:
calculating a time-decayed quantile.
25. The non-transitory computer readable medium of claim 19 wherein said computer program instructions defining the step of calculating a time-decayed aggregate further comprise computer instructions defining the step of:
calculating a time-decayed heavy hitter.