FORWARD DECAY TEMPORAL DATA ANALYSIS

• US 20110066600A1
• Filed: 09/15/2009
• Published: 03/17/2011
• Est. Priority Date: 09/15/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Shkapenyuk, Vladislav, Xu, Bojian, Cormode, Graham, Srivastava, Divesh
• Granted Patent: US 8,595,194 B2
• Time in Patent Office: Days
• US Class Current: 707/689
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

A disclosed method for implementing time decay in the analysis of streaming data objects is based on the age, referred to herein as the forward age, of a data object measured from a landmark time in the past to a time associated with the occurrence of the data object, e.g., an object'"'"'s timestamp. A forward time decay function is parameterized on the forward age. Because a data object'"'"'s forward age does not depend on the current time, a value of the forward time decay function is determined just once for each data object. A scaling factor or weight associated with a data object may be weighted according to its decay function value. Forward time decay functions are beneficial in determining decayed aggregates, including decayed counts, sums, and averages, decayed minimums and maximums, and for drawing decay-influenced samples.

Claims

1. A method for calculating time decay associated with data objects arriving at a data management system, comprising:

determining a forward age associated with a data object based on a difference between an arrival time of the data object at the data management system and a landmark time prior to the arrival time;

recording the forward age in a memory media; and

weighting a parameter value associated with the data object with a decay function based on the current time and the forward age, wherein the forward age associated with the data object does not change as time elapses.

2. The method of claim 1, further comprising:

calculating a forward time decayed holistic aggregate based on the weighted parameter values of a plurality of data objects, wherein the forward time decayed holistic aggregate is selected from a forward time decayed heavy hitter and a forward time decayed quantile.

3. The method of claim 1, further comprising:

calculating a forward time decayed aggregate based on the weighted parameter values of a plurality of data objects, wherein the forward time decayed aggregate is selected from a forward time decayed count, a forward time decayed sum, a forward time decayed average, and a forward time decayed variance.

4. The method of claim 1, further comprising:

calculating at least one of a forward time decayed minimum and a forward time decayed maximum.

5. The method of claim 1, further comprising:

drawing a forward time decayed sample without replacement from a population of the data objects, wherein selection of the forward time decayed sample depends on the weighted parameter values of the population of the data objects.

6. The method of claim 1, further comprising:

drawing a forward time decayed sample with replacement from a population of the data objects, wherein selection of the forward time decayed sample depends on the weighted parameter values of the population of the data objects.

7. The method of claim 1, wherein the decay function is selected from an exponential function and a polynomial function, and a landmark window function.

8. A computer system for calculating time decay associated with arriving data objects comprising:

a processor; and

memory media accessible to the processor, including processor executable instructions to;

upon arrival of a data object, determine a forward age associated with the data object based on a difference between an arrival time of the data object and a landmark time prior to the arrival time; and

weight a parameter value associated with the data object based on the forward age and a value of a decay function, wherein the forward age associated with the data object remains a constant.

9. The computer system of claim 8, wherein the decay function value depends on the current time.

10. The computer system of claim 9, further comprising processor executable instructions to:

calculate a decayed count for a plurality of arriving data objects, wherein the decayed count is a sum of the decay function value over the arriving data objects.

11. The computer system of claim 9, further comprising processor executable instructions to:

calculate a decayed sum for a plurality of arriving data objects, wherein the decayed sum is a sum of the weighted value over the arriving data objects.

12. The computer system of claim 9, further comprising processor executable instructions to:

calculate a decayed average for a plurality of arriving data objects, wherein the decayed average is a ratio of a decayed sum to a decayed count, wherein the decayed count is a sum of the decay function value over the arriving data objects, and wherein the decayed sum is a sum of the weighted value over the arriving data objects.

13. The computer system of claim 9, further comprising processor executable instructions to:

determine which of a plurality of data objects has the highest weighted value; and

determine which of the plurality of data objects has the lowest weighted value.

14. The computer system of claim 9, wherein the decay function is selected from an exponential function, a polynomial function, and a landmark window function.

15. Computer-readable memory media, including instructions for applying a time decay function to streaming data objects, said instructions executable to:

upon arrival of a data object, determine a forward age associated with the data object based on a difference between an arrival time of the data object and a landmark time prior to the arrival time; and

associate a weighted value with the data object, wherein the weighted value depends on a decay function and the forward age, wherein the forward age associated with the data object is a constant.

16. The memory media of claim 15, further comprising instructions executable to:

store the forward age to a memory media.

17. The memory media of claim 15, further comprising instructions executable to:

calculate the decay function based on the current time.

18. The memory media of claim 15, further comprising instructions executable to:

apply the weighted value to a parameter value associated with the data object.

19. The memory media of claim 15, further comprising instructions executable to:

determine a forward time decayed aggregate of a plurality of data objects based, at least in part, on weighted values corresponding to the plurality of data objects, wherein the forward time decayed aggregate is selected from;

a forward time decayed count aggregate, a forward time decayed sum aggregate, a forward time decayed average aggregate, and a forward time decayed variance.

20. The memory media of claim 15, further comprising instructions executable to:

draw a forward time decayed sample from a plurality of data objects, wherein the sample is based, at least in part, on weighted values associated with the data objects.