# US 2005/0038769 A1 · Methods and apparatus for clustering evolving data streams through online and offline components

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

- Number: US 2005/0038769 A1
- Document ID: US20050038769A1
- Status: Published application
- Kind: A1
- Application number: 10/641,951
- Filed: 2003-08-14
- Published: 2005-02-17
- Earliest claimed: 2003-08-14
- Assignees: International Business Machines Corporation
- Inventors: Charu Aggarwal; Philip Yu
- Web page: https://patentgrep.com/patent/US20050038769A1

## CPC

- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F 16/285: {Clustering or classification}
- Y10S 707/99931: Database or file accessing
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A technique of clustering data of a data stream is provided. Online statistics are first created from the data stream. Offline processing of the online statistics is then performed when offline processing either required or desired. Online statistics may be created through the reception of data points from the data stream and the formation and updating of data groups. Offline processing may be performed by reclustering groups of data points around sampled data points and reporting the newly formed clusters.

## Claims

### Claim 1

A method of clustering data of a data stream comprising the steps of:
creating online statistics from the data stream; and
performing offline processing of the online statistics when offline processing is one of required and desired.

### Claim 2 (depends on 1)

The method of claim 1, further comprising the step of determining whether offline processing is one of required and desired.

### Claim 3 (depends on 1)

The method of claim 1, wherein the step of creating online statistics comprises the steps of:
receiving a data point from the data stream; and
updating the online statistics from the data stream.

### Claim 4 (depends on 3)

The method of claim 3, wherein the step of updating online statistics comprises the steps of:
finding a group of data points closest to the data point;
determining if a distance to the closest group is greater than a threshold;
creating a new group having the data point if the distance to the closest group is greater than the threshold;
adding the data point to the closest group if the distance to the closest group is less than the threshold; and
updating the statistics of the new group if created or closest group if the data point was added.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of performing off-line processing comprises the steps of:
sampling a defined number of data points;
re-clustering groups of data points around the sampled data points;
determining if additional iterations of sampling and re-clustering are required;
redefining the sampled points as centroids of the reclustered groups of data points if additional iterations are required, before re-clustering groups of data points around the redefined sampled points; and
reporting clusters formed in the re-clustering.

### Claim 6 (depends on 1)

The method of claim 1, wherein the step of performing offline processing comprises the step of utilizing the online statistics to create higher level clusters.

### Claim 7 (depends on 6)

The method of claim 6, wherein the online statistics are lower-level clusters.

### Claim 8 (depends on 7)

The method of claim 7, wherein the step of utilizing the online statistics to create higher level clusters comprises the step of re-clustering lower level clusters.

### Claim 9 (depends on 1)

The method of claim 1, wherein the step of performing offline processing comprises the step of utilizing the online statistics to monitor data stream evolution.

### Claim 10 (depends on 9)

The method of claim 9, wherein the step of utilizing the online statistics to monitor data stream evolution comprises the step of comparing the online statistics at two different horizons.

### Claim 11 (depends on 9)

The method of claim 9, wherein the step of utilizing the online statistics to monitor data stream evolution comprises the steps of:
subtracting online statistics over specified horizons; and
determining evolution classification based on subtracted statistics.

### Claim 12 (depends on 1)

The method of claim 1, further comprising the step of storing online statistics at specific times depending upon a pyramidal distribution.

### Claim 13

Apparatus for clustering data of data stream, the apparatus comprising:
a memory; and
at least one processor coupled to the memory and operative to: (i) create online statistics from the data stream; and (ii) perform offline processing of the online statistics when offline processing is one of required and desired.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the at least one processor is further operative to determine whether offline processing is one of required and desired.

### Claim 15 (depends on 13)

The apparatus of claim 13, wherein the operation of creating online statistics is operative to:
receive a data point from the data stream; and
update the online statistics from the data stream.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the operation of updating online statistics is operative to:
find a group of data points closest to the data point;
determine if a distance to the closest group is greater than a threshold;
create a new group having the data point if the distance to the closest group is greater than the threshold;
add the data point to the closest group if the distance to the closest group is less than the threshold; and
update the statistics of the new group if created or closest group if the data point was added.

### Claim 17 (depends on 13)

The apparatus of claim 13, wherein the operation of performing off-line processing is operative to:
sample a defined number of data points;
re-cluster groups of data points around the sampled data points;
determine if additional iterations of sampling and re-clustering are required;
redefine the sampled points as centroids of the reclustered groups of data points if additional iterations are required, before re-clustering groups of data points around the redefined sampled points; and
report clusters formed in the re-clustering.

### Claim 18 (depends on 13)

The apparatus of claim 13, wherein the operation of performing offline processing is operative to utilize the online statistics to create higher level clusters.

### Claim 19 (depends on 13)

The apparatus of claim 13, wherein the online statistics are lower-level clusters.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the operation of utilizing the online statistics to create higher level clusters is operative to re-cluster lower level clusters.

### Claim 21 (depends on 13)

The apparatus of claim 13, wherein the operation of performing offline processing is operative to utilize the online statistics to monitor data stream evolution.

### Claim 22 (depends on 21)

The apparatus of claim 21, wherein the operation of utilizing the online statistics to monitor data stream evolution is operative to compare the online statistics at two different horizons.

### Claim 23 (depends on 21)

The apparatus of claim 21, wherein the operation of utilizing the online statistics to monitor data stream evolution is operative to:
subtract online statistics over specified horizons; and
determine evolution classification based on subtracted statistics.

### Claim 24 (depends on 13)

The apparatus of claim 13, wherein the at least one processor is further operative to store online statistics at specific times depending upon a pyramidal distribution.

### Claim 25

An article of manufacture for clustering data of a data stream, comprising a machine readable medium containing one or more programs which when executed implement the steps of:
creating online statistics from the data stream; and
performing offline processing of the online statistics when offline processing is one of required and desired.
