Method and apparatus for processing data streams

• US 20060282425A1
• Filed: 04/20/2005
• Published: 12/14/2006
• Est. Priority Date: 04/20/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Granted Patent: US 7,739,284 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions

Abstract

Techniques are disclosed for clustering and classifying stream data. By way of example, a technique for processing a data stream comprises the following steps/operations. A cluster structure representing one or more clusters in the data stream is maintained. A set of projected dimensions is determined for each of the one or more clusters using data points in the cluster structure. Assignments are determined for incoming data points of the data stream to the one or more clusters using distances associated with each set of projected dimensions for each of the one or more clusters. Further, the cluster structure may be used for classification of data in the data stream.

Claims

1. A method of processing a data stream, comprising the steps of:

maintaining a cluster structure, the cluster structure representing one or more clusters in the data stream;

determining a set of projected dimensions for each of the one or more clusters using data points in the cluster structure; and

determining assignments for incoming data points of the data stream to the one or more clusters using distances associated with each set of projected dimensions for each of the one or more clusters.

2. The method of claim 1, wherein the assignment determining step further comprises assigning an incoming data point to a closest cluster of the one or more clusters when the incoming data point lies inside a boundary of the closest cluster.

3. The method of claim 2, wherein the assigning step further comprises determining the boundary of a cluster using a radius of the cluster.

4. The method of claim 1, wherein the assignment determining step further comprises assigning an incoming data point to a newly created cluster when the incoming data point lies outside a boundary of a closest cluster.

5. The method of claim 1, wherein the assignment determining step further comprises assigning the incoming data point to a closest cluster using the corresponding set of projected dimensions.

6. The method of claim 1, wherein the assignment determining step further comprises determining a distance of the incoming data point to each cluster using the corresponding set of dimensions for each cluster.

7. The method of claim 1, wherein the dimension set determining step further comprises using a variance along individual dimensions to determine the sets of projected dimensions.

8. The method of claim 7, wherein the dimension set determining step further comprises selecting sets of projected dimensions with the least variance.

9. The method of claim 1, further comprising the step of using the cluster structure for classification of data in the data stream.

10. The method of claim 9, wherein the cluster structure maintaining step further comprises maintaining the one or the clusters in a class-specific manner.

11. The method of claim 10, further comprising the step of identifying a class label of a closest cluster as the relevant label with respect to the data being classified.

12. Apparatus for processing a data stream, comprising:

a memory; and

at least one processor operative to;

(i) maintain a cluster structure, the cluster structure representing one or more clusters in the data stream;

(ii) determine a set of projected dimensions for each of the one or more clusters using data points in the cluster structure; and

(iii) determine assignments for incoming data points of the data stream to the one or more clusters using distances associated with each set of projected dimensions for each of the one or more clusters.

13. The apparatus of claim 12, wherein the assignment determining operation further comprises assigning an incoming data point to a closest cluster of the one or more clusters when the incoming data point lies inside a boundary of the closest cluster.

14. The apparatus of claim 13, wherein the assigning operation further comprises determining the boundary of a cluster using a radius of the cluster.

15. The apparatus of claim 12, wherein the assignment determining operation further comprises assigning an incoming data point to a newly created cluster when the incoming data point lies outside a boundary of a closest cluster.

16. The apparatus of claim 12, wherein the assignment determining operation further comprises assigning the incoming data point to a closest cluster using the corresponding set of projected dimensions.

17. The apparatus of claim 12, wherein the assignment determining operation further comprises determining a distance of the incoming data point to each cluster using the corresponding set of dimensions for each cluster.

18. The apparatus of claim 12, wherein the dimension set determining operation further comprises using a variance along individual dimensions to determine the sets of projected dimensions.

19. The method of claim 18, wherein the dimension set determining operation further comprises selecting sets of projected dimensions with the least variance.

20. The apparatus of claim 12, wherein the at least one processor is further operative to use the cluster structure for classification of data in the data stream.

21. The apparatus of claim 20, wherein the cluster structure maintaining operation further comprises maintaining the one or the clusters in a class-specific manner.

22. The method of claim 21, wherein the at least one processor is further operative to identify a class label of a closest cluster as the relevant label with respect to the data being classified.

23. Apparatus, comprising:

a server, responsive to a data stream associated with one or more client devices, operative to;

(i) maintain a cluster structure, the cluster structure representing one or more clusters in the data stream;

(ii) determine a set of projected dimensions for each of the one or more clusters using data points in the cluster structure; and

(iii) determine assignments for incoming data points of the data stream to the one or more clusters using distances associated with each set of projected dimensions for each of the one or more clusters.

24. An article of manufacture for use in processing a data stream, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

maintaining a cluster structure, the cluster structure representing one or more clusters in the data stream;

determining a set of projected dimensions for each of the one or more clusters using data points in the cluster structure; and

determining assignments for incoming data points of the data stream to the one or more clusters using distances associated with each set of projected dimensions for each of the one or more clusters.