Forward decay temporal data analysis

• US 8,595,194 B2
• Filed: 09/15/2009
• Issued: 11/26/2013
• Est. Priority Date: 09/15/2009
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Shkapenyuk, Vladislav, Srivastava, Divesh, Xu, Bojian
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US12/560,214
• Publication Number:
  US 20110066600A1
• Time in Patent Office: 1,533 Days
• Field of Search: 707/689
• 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 arriving data objects, the method comprising:

determining a forward age associated with a data object arriving at a data management system 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;

determining a decay age associated with the data object based on a difference between a current time and the arrival time of the data object;

recording the forward age in a memory media; and

calculating a time decay associated with the data object, wherein the calculating a time decay associated with the data object includes;

and

weighting a parameter value associated with the data object with a decay function based on the decay age and the forward age, wherein the forward age associated with the data object does not change as time elapses, wherein the decay function is selected from an exponential function, a polynomial function, and a landmark window function;

calculating an age factor for the data object based on the weighted parameter value;

ranking a plurality of data objects object based on the age factor to determine a highest and lowest ranking data object; and

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.

2. The method of claim 1, further comprising calculating a forward time decayed aggregate based on the weighted parameter values of the 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.

3. The method of claim 1, further comprising calculating a forward time decayed minimum.

4. The method of claim 1, further comprising drawing a forward time decayed sample without replacement from a population of the plurality of data objects, wherein selection of the forward time decayed sample depends on the weighted parameter values of the population of the plurality of data objects.

5. The method of claim 1, further comprising drawing a forward time decayed sample with replacement from a population of the plurality of data objects, wherein selection of the forward time decayed sample depends on the weighted parameter values of the population of the plurality of data objects.

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

a processor; and

memory storing instructions that, when executed by the processor, perform operations including;

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

determining a decay age associated with the data object based on a difference between a current time and the arrival time of the data object;

recording the forward age in the memory;

calculating a time decay associated with the data object, wherein the calculating the time decay associated with the data object includes;

weighting a parameter value associated with the data object based on the forward age and on the decay age, wherein the forward age associated with the data object remains a constant, and wherein the decay function is selected from an exponential function, a polynomial function, and a landmark window function;

calculating an age factor for the data object based on the weighting of the parameter value;

ranking a plurality of data objects object based on the age factor to determine a highest ranking data object and a lowest ranking data object; and

calculating a forward time decayed holistic aggregate based on the weighted parameter values of the 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.

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

8. The computer system of claim 7, wherein the operations further include calculating 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.

9. The computer system of claim 7, wherein the operations further include calculating 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.

10. The computer system of claim 7, wherein the operations further include calculating 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.

11. The computer system of claim 7, wherein the operations further include:

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

determining which of the plurality of data objects has a lowest weighted value.

12. A non-transitory computer readable storage medium including stored program instruction that, when executed by a processor causes a computer to calculate time decay associated with arriving data objects, comprising:

determining a forward age associated with a data object arriving at a data management system 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;

determining a decay age associated with the data object based on a difference between a current time and the arrival time of the data object;

recording the forward age in a memory media;

calculating time decay associated with the data object, wherein the calculating of the time decay associated with the data object includes;

weighting a parameter value associated with the data object with a decay function based on the decay age and the forward age, wherein the forward age associated with the data object remains constant as time elapses, wherein the decay function is selected from an exponential function, a polynomial function, and a landmark window function;

calculating an age factor for the data object based on the weighting of the parameter value;

ranking a plurality of data objects based on the age factor to determine a highest ranking data object and a lowest ranking data object; and

calculating a forward time decayed holistic aggregate based on the weighted parameter values of the 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.

13. The non-transitory computer readable storage medium of claim 12, wherein the operations include calculating calculate the decay function based on the current time.