Patent ID: 7836090

Claim:
In a system including a computer for performing a clustering analysis on a data set residing in a memory operably coupled to the computer, the data set represented as a relational table R of n tuples, each tuple having at least one numeric attribute and a class label of a class to which the tuple belongs, a computer implemented method comprising: converting each numeric attribute into a binary representation having b-bit positions; decomposing the dataset into a bit sequential format (bSQ) comprising b separate bit vectors, with one bit vector for each of the b-bit positions; constructing at least one basic Peano-Count tree (P-tree) P ij representing a P-tree for the j th bit vector of the i th attribute from the bSQ formatted dataset wherein the P-tree is obtained by: designating at a root node a root count (rc) representing the sum of 1-bits in the j th bit vector; and recursively partitioning the j th bit vector into subsets and recording the root count of 1-bit for each subset at a leaf node until a subset has all 0-bits or all 1-bits; obtaining at least one P-tree class mask PX comprising a vertical bit vector for each class X with bit 1 assigned to each tuple containing class X and bit 0 assigned to the tuple otherwise; defining a P-tree algebra having at least one logical AND (^) operator representing a resultant P-tree obtained by level-by-level ANDing of the corresponding nodes or leaves of a first P-tree with a second P-tree; using the P-tree algebra to formulate a Vertical Set Inner Product (VSIP) for a selected class X having vectors xεX in R with P-tree class mask PX, with a target vector aεR, the VSIP formulated according to a first relation X · a = ∑ x ∈ X ⁢ ⁢ x · a = ∑ i = 1 n ⁢ ⁢ ∑ j = b - 1 0 ⁢ ⁢ rc ⁡ ( PX ⋀ P ij ) · ∑ k = 0 b - 1 ⁢ ⁢ 2 j + k · a ik where x and a are represented in b binary bits; repeatedly performing until X is empty; selecting a point aεX having a local density ρ, and computing a VSIP for all xεX that lies within a disk of radius r centered about point a, wherein r is progressively increased until r=r max , at which point a local density variation exceeds a predefined threshold value; defining a revised set, (X−x), that excludes all points xεX that lie within disk of radius r max and having a local density substantially equal to the local density ρ about a; and tabulating the point aε(X−x), the r max , the local density ρ and the local density variation to generate a table T; and sorting the table T on the VSIP to obtain a ranked set of centroids for use in the cluster analysis.