Method and apparatus for processing data streams

• US 7,739,284 B2
• Filed: 04/20/2005
• Issued: 06/15/2010
• Est. Priority Date: 04/20/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Ng; Amy
• Application Number:
  US11/110,079
• Publication Number:
  US 20060282425A1
• Time in Patent Office: 1,882 Days
• Field of Search: 707/104.1, 707/202, 707/201, 707/204, 707/737, 707/803, 707/809
• US Class Current: 707/737
• 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

A technique for processing a data stream includes 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 maybe used for classification of data in the data stream.

Claims

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

maintaining a cluster structure, the cluster structure representing one or more clusters in the continuously progressing data stream, wherein the cluster structure comprises one or more data points in a multidimensional space, further wherein the one or more data points of the cluster structure fade as the continuously progressing data stream progresses;

determining a set of projected dimensions for each of the one or more clusters using the one or more data points in the cluster structure, a given set of projected dimensions of a cluster being associated with a subset of a total number of dimensions of the continuously progressing data stream and the given set of projected dimensions being represented by a d-dimensional bit vector such that dimensions of the d dimensions in the bit vector that are present in the cluster are assigned one value and dimensions of the d dimensions in the bit vector that are not in the cluster are assigned another value, the given set of projected dimensions being continuously redefined to minimize a cluster radius, wherein redefining the set of projected dimensions comprises varying the values of the bit vector based on which dimensions are present and not present in the cluster as the data stream progresses and the one or more data points fade; and

determining assignments for incoming data points of the continuously progressing 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;

wherein one or more of the steps of maintaining the cluster structure, determining the set of projected dimensions, and determining the assignments are implemented as one or more software components that are loaded from a memory and executed by a processor.

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 continuously progressing data stream.

10. The method of claim 9, wherein the cluster structure maintaining step further comprises maintaining the one or more 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 continuously progressing data stream, comprising:

a memory; and

at least one processor coupled to the memory, the at least one processor being operative to;

(i) maintain a cluster structure, the cluster structure representing one or more clusters in the continuously progressing data stream, wherein the cluster structure comprises one or more data points in a multidimensional space, further wherein the one or more data points of the cluster structure fade as the continuously progressing data stream progresses;

(ii) determine a set of projected dimensions for each of the one or more clusters using the one or more data points in the cluster structure, a given set of projected dimensions of a cluster being associated with a subset of a total number of dimensions of the continuously progressing data stream and the given set of projected dimensions being represented by a d-dimensional bit vector such that dimensions of the d dimensions in the bit vector that are present in the cluster are assigned one value and dimensions of the d dimensions in the bit vector that are not in the cluster are assigned another value, the given set of projected dimensions being continuously redefined to minimize a cluster radius, wherein redefining the set of projected dimensions comprises varying the values of the bit vector based on which dimensions are present and not present in the cluster as the data stream progresses and the one or more data points fade; and

(iii) determine assignments for incoming data points of the continuously progressing 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 apparatus 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 continuously progressing data stream.

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

22. The apparatus 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 continuously progressing data stream associated with one or more client devices, the server comprising;

a memory and at least one processor coupled to the memory, the at least one processor being operative to;

(i) maintain a cluster structure, the cluster structure representing one or more clusters in the continuously progressing data stream, wherein the cluster structure comprises one or more data points in a multidimensional space, further wherein the one or more data points of the cluster structure fade as the continuously progressing data stream progresses;

(ii) determining a set of projected dimensions for each of the one or more clusters using the one or more data points in the cluster structure, a given set of projected dimensions of a cluster being associated with a subset of a total number of dimensions of the continuously progressing data stream and the given set of projected dimensions being represented by a d-dimensional bit vector such that dimensions of the d dimensions in the bit vector that are present in the cluster are assigned one value and dimensions of the d dimensions in the bit vector that are not in the cluster are assigned another value, the given set of projected dimensions being continuously redefined to minimize a cluster radius, wherein redefining the set of projected dimensions comprises varying the values of the bit vector based on which dimensions are present and not present in the cluster as the data stream progresses and the one or more data points fade; and

(iii) determine assignments for incoming data points of the continuously progressing 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 continuously progressing data stream, the article comprising a computer readable storage 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 continuously progressing data stream, wherein the cluster structure comprises one or more data points in a multidimensional space, further wherein the one or more data points of the cluster structure fade as the continuously progressing data stream progresses;

determining a set of projected dimensions for each of the one or more clusters using the one or more data points in the cluster structure, a given set of projected dimensions of a cluster being associated with a subset of a total number of dimensions of the continuously progressing data stream and the given set of projected dimensions being represented by a d-dimensional bit vector such that dimensions of the d dimensions in the bit vector that are present in the cluster are assigned one value and dimensions of the d dimensions in the bit vector that are not in the cluster are assigned another value, the given set of projected dimensions being continuously redefined to minimize a cluster radius, wherein redefining the set of projected dimensions comprises varying the values of the bit vector based on which dimensions are present and not present in the cluster as the data stream progresses and the one or more data points fade; and

determining assignments for incoming data points of the continuously progressing 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.