US 5,832,182 AGranted

Method and system for data clustering for very large databases

AssigneeWisconsin Alumni Research Foundation

InventorsTian Zhang, Raghu Ramakrishnan, Miron Livny

Life of this patent

Estimating the term…

Loading patent…

Abstract

Multi-dimensional data contained in very large databases is efficiently and accurately clustered to determine patterns therein and extract useful information from such patterns. Conventional computer processors may be used which have limited memory capacity and conventional operating speed, allowing massive data sets to be processed in a reasonable time and with reasonable computer resources. The clustering process is organized using a clustering feature tree structure wherein each clustering feature comprises the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster. A dense region of data points is treated collectively as a single cluster, and points in sparsely occupied regions can be treated as outliers and removed from the clustering feature tree. The clustering can be carried out continuously with new data points being received and processed, and with the clustering feature tree being restructured as necessary to accommodate the information from the newly received data points.

Claims34

Dependent claims

A method of clustering data, provided by a data source, in a computer processor having a main memory with a limited capacity, comprising the steps of:

(a) receiving data points from the data source;
(b) determining clusters of the data points that are within a selected threshold and determining a clustering feature for each such cluster, the clustering feature comprising the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, and storing the clustering feature for each cluster in the main memory;
and
(c) forming a clustering feature tree comprised of leaf nodes including leaf entries and at least one level of nodes joined to the leaf nodes, the leaf entries of the tree comprising the clustering features of the clusters, the next highest nodes in the tree above the leaves comprising nonleaf nodes that are each joined to a selected number of different leaves, the selected number comprising a branch number, each nonleaf node distinguished by identifiers stored in the main memory comprising the clustering features of each leaf to which the nonleaf node is joined and pointers indicating the leaves to which the node is joined, and further comprising, as necessary, higher level nodes joined to the branch number of lower level nodes, each higher level node distinguished by identifiers that are stored to main memory which comprise the clustering features for each lower node to which the higher node is joined and pointers indicating the lower nodes to which the higher node is joined, the tree terminating at a root node.

1 more element

A processing system for clustering data points provided by a data source, comprising:

(a) a computer processor;
(b) a main memory connected to the processor;
(c) an ancillary memory connected to the processor;
(d) means for receiving the data points from the data source for access by the processor;
(e) means in the processor for analyzing the data points to determine clusters of the data points and to determine a clustering feature for each such cluster which comprises the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, and means for storing the clustering feature so determined for each cluster in the main memory.

2 more elements

A processing system for clustering data points provided by a data source comprising:

(a) a computer processor;
(b) a main memory connected to the processor, the main memory having a clustering feature tree stored therein comprised of leaf nodes including leaf entries and at least one level of nodes joined to the leaf nodes, the leaf entries of the tree comprising clustering features of the cluster, each clustering feature comprising the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, the next highest nodes in the tree above the leaves comprising nonleaf nodes that are each joined to a selected number of different leaves, the selected number comprising a branch number, each nonleaf node distinguished by identifiers stored in the main memory comprising the clustering features of each leaf to which the nonleaf node is joined and pointers indicating the leaves to which the node is joined, and further comprising, as necessary, higher level nodes joined to the branch number of lower level nodes, each higher level node distinguished by identifiers that are stored to main memory which comprise the clustering features for each lower node to which the higher node is joined and pointers indicating the lower nodes to which the higher node is joined, the tree terminating at a root node;
(c) an ancillary memory connected to the processor;
(d) means for receiving the data points from the data source for access by the processor;
(e) means in the processor for receiving a new data point and assigning it to the clustering feature tree by, starting at the root node, assigning the data point to the lower level node that is closest to the data point in accordance with a selected distance measurement using the clustering feature for the lower level node, and continuing down through each of the levels in the tree by assigning the new data point to the closest lower level node by a selected distance measurement until the closest leaf is found in accordance with the selected distance measurement;
and
(f) means for testing the new data point to determine if the new data point is within a selected threshold distance to the closest leaf entry in accordance with the selected distance measurement and if so, revising the clustering feature for the closest leaf entry by adding to it the clustering feature values for the new data point and writing the revised clustering feature for the closest leaf entry to main memory, and if the new data point is not within the threshold, identifying the new data as a cluster and a new leaf entry, and if the leaf node containing the new leaf entry cannot accommodate the total number of leaf entries, splitting the leaf node to form two leaf nodes which are comprised of leaf entries, and then updating all of the clustering feature identifiers for higher nodes which are on a path to the leaf node and if a split of a leaf node has occurred, splitting higher nodes if necessary to accommodate the split leaf node so that the branch number is not exceeded.

4 more elements

Dependencies are inferred from the claim text.