# US 2013/0155892 A1 · Computing Time-Decayed Aggregates in Data Streams

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0155892 A1
- Document ID: US20130155892A1
- Status: Published application
- Kind: A1
- Application number: 13/755,621
- Filed: 2013-01-31
- Published: 2013-06-20
- Earliest claimed: 2008-01-02
- Assignees: Iowa State University Research Foundation, Inc.; AT&T Intellectual Property I, L.P.
- Inventors: Graham Cormode; Philip Korn; Srikanta Tirthapura
- Web page: https://patentgrep.com/patent/US20130155892A1

## CPC

- H04L 43/00: Arrangements for monitoring or testing data switching networks
- H04L 43/106: using time related information in packets, e.g. by adding timestamps
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

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 out-of-order, that is, the sequence in which the tuples arrive are not necessarily in the sequence of their corresponding timestamps. In calculating aggregates, more recent data may be given more weight by multiplying each tuple by a decay function which is a function of the timestamp associated with the tuple and the current time. The tuples are recorded in a quantile-digest data structure. Aggregates are calculated from the data stored in the quantile-digest data structure.

## Claims

### Claim at position 1

1-25. (canceled)

### Claim 26

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.

### Claim 27 (depends on 26)

The apparatus of claim 26, wherein the quantile-digest data structure comprises a set of quantile-digests.

### Claim 28 (depends on 26)

The apparatus of claim 26, wherein the operations further comprise compressing the quantile-digest data structure.

### Claim 29 (depends on 26)

The apparatus of claim 26, wherein the decay function is a sliding-window function.

### Claim 30 (depends on 26)

The apparatus of claim 26, wherein the decay function is an exponential decay function.

### Claim 31 (depends on 26)

The apparatus of claim 26, wherein the decay function is a polynomial decay function.

### Claim 32 (depends on 26)

The apparatus of claim 26, wherein the time-decayed aggregate is a time-decayed user-defined aggregate function.

### Claim 33 (depends on 26)

The apparatus of claim 26, wherein the time-decayed aggregate is a time-decayed count.

### Claim 34 (depends on 26)

The apparatus of claim 26, wherein the time-decayed aggregate is a time-decayed range.

### Claim 35 (depends on 26)

The apparatus of claim 26, wherein the time-decayed aggregate is a time-decayed quantile.

### Claim 36 (depends on 26)

The apparatus of claim 26, wherein the time-decayed aggregate is a time-decayed heavy hitter.
