Multidimensional data clustering and dimension reduction for indexing and searching

Claim 2

A computerized method of representing multidimensional data, comprising the steps of: a) partitioning the multidimensional data into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; d) storing the dimensionality reduction information; e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and f) generating and storing one or more low-dimensional idexes for clusters at a lowest level of said hierarchy.

Claim 3

The method of claim 1, further comprising the steps of: (a) generating cluster boundaries, which correspond to a zeroth-order approximation to a geometry of said clusters; (b) approximating the geometry of each of the clusters by means of a minimum bounding box and generating a first-order approximation to the geometry of each cluster; (c) partitioning the bounding box into 2 k hyper rectangles, wherein said partitioning is at a midpoint of each dimension; (d) retaining only those hyper rectangles that contain data points and generating a second-order approximation to the geometry of the cluster; and (e) repeating said steps (c) and (d) for each retained hyper rectangle to generate successively the third-, fourth-, . . . , n-th approximations to the geometry of the cluster.

Claim 4

The method of claim 2, for searching a hierarchy of approximations to the geometric structure of each cluster, further comprising the steps of: reducing the dimensionality of the specified data using the dimensionality reduction information associated with the database; finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; assessing whether one or more other clusters can contain records closer to the specified data than the farthest of the k records retrieved; retaining an other cluster only if it can contain any of k-nearest neighbors of specified data based on boundaries of the cluster; iteratively determining if a retained cluster could contain any of the k-nearest neighbors, based on increasingly finer approximations to the geometry, and retaining the retained cluster only if the cluster is accepted at the finest level of the hierarchy of successive approximations; and identifying a retained cluster as a candidate cluster containing one or more of the k-nearest neighbors of the data, in response to said step of iteratively determining.

Claim 5

The method of claim 1, further comprising the step of storing the index entirely in the main memory of a computer.

Claim 6

The method of claim 1, wherein said generating a reduced dimensionality cluster comprises a singular value decomposition further comprising the steps of: producing a transformation matrix and eigenvalues of the transformation matrix for said each cluster; and selecting a subset of the eigenvalues including the largest eigenvalues; wherein the dimensionality reduction information includes the transformation matrix and the subset of the eigenvalues.

Claim 7

The method of claim 5, for searching for k most similar records to specified data using the reduced dimensionality index, comprising the steps of: associating specified data to said one or more clusters, based on stored clustering information; projecting the specified data onto a subspace for an associated cluster based on stored dimensionality reduction information for the associated cluster; generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting; searching, via the index, for the associated cluster having k most similar records to the projected specified data; determining if any other associated cluster can include any of k most similar records to the projected specified data; and repeating said searching on said any cluster that can include any of the k most similar records to the specified data.

Claim 8

The method of claim 6, wherein said searching, via the index, for the associated cluster further comprises the step of: computing the distances (D) between k nearest neighbors in the associated cluster and the projected specified data as a function of a mismatch index δ 2 wherein, δ.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ∥orthogonal.sub.-- complement∥.sup.2. 8.

Claim 9

The method of claim 6, wherein the specified data includes a search template, further comprising the steps of: said projecting step further comprising the step of projecting the template, using the dimensionality reduction information, onto a subspace associated with the cluster to which it belongs; generating template dimensionality reduction information for a projected template; wherein said searching, via the index is based on the projected template and the template dimensionality reduction information; and updating a set of the k most similar records to the search template.

Claim 10

The method of claim 5, wherein said selecting a subset of the eigenvalues is a function of a precision and a recall of returned results.

Claim 11

The method of claim 1, for searching for k records most similar to specified data, the method for searching comprising the steps of: identifying a cluster to which specified data belongs, based on the clustering information; reducing the dimensionality of the specified data based on the dimensionality reduction information for an identified cluster; generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; searching the multidimensional index, using the dimensionality reduction information, for a reduced-dimensionality version of the cluster to which the specified data belongs; retrieving via the multidimensional index, the k most similar records in the cluster; identifying other candidate clusters which can contain records closer to the specified data than the farthest of the k most similar records retrieved; searching a closest other candidate cluster to the specified data, in response to said identifying step; and repeating said identifying and searching steps for all said other candidate clusters.

Claim 12

The method of claim 10, further comprising the step of: computing the distances (D) between k nearest neighbors in the version of the cluster and the projected specified data as a function of a mismatch index δ 2 wherein, δ.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ∥orthogonl.sub.-- complement∥.sup.2. 12.

Claim 13

The method of claim 1, wherein the clustering information includes information on a centroid of said one or more clusters, further comprising the step of associating the centroid with a unique label.

Claim 14

The method of claim 1, wherein the dimensionality of the data is >8.

Claim 15

The method of claim 1, for performing an exact search, comprising the steps of: associating specified data to one of the clusters based on stored clustering information; reducing the dimensionality of the specified data based on stored dimensionality reduction information for a reduced dimensionality version of a cluster, in response to said associating step; and searching, based on reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

Claim 16

The method of claim 14, wherein said searching further comprises the step of conducting a linear scan to match the specified data.

Claim 17

The method of claim 1 wherein the data is stored in one of a spatial database or a multimedia database which includes a plurality of data records each containing a plurality of fields, further comprising the steps of: creating a representation of the database to be indexed as a set of vectors, where each vector corresponds to a row in the database and the elements of each vector correspond to the values, for a particular row, contained in the columns for which the searchable index will be generated; and said partitioning comprising partitioning the vectors into said one or more clusters.

Claim 18

The method of claim 1, for performing an exact search, comprising the steps of: recursively applying the steps of: finding a cluster to which specified data belongs, using stored clustering information; and reducing the dimensionality of the specified data using stored dimensionality reduction information, until a corresponding lowest level of the hierarchy of reduced dimensionality clusters has been reached; and searching, using the low dimensional indexes, for a reduced dimensionality version of the cluster matching the specified data.

Claim 19

The method of claim 1, for performing a similarity search, further comprising the steps of: recursively applying the steps of: finding the cluster to which specified data belongs, using stored clustering information; and reducing the dimensionality of the specified data to correspond to the lowest level of the hierarchy of reduced dimensionality clusters, using stored dimensionality reduction information; searching for candidate terminal clusters that can contain one or more of k nearest neighbors of the specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and for each candidate terminal cluster; performing an intra-cluster search for the k nearest neighbors to the specified data.

Claim 20

The method of claim 1, for performing a similarity search, further comprising the steps of: reducing the dimensionality of the specified data; recursively applying the steps of: finding the cluster to which reduced dimensionality specified data belongs, using stored clustering information; and reducing the dimensionality of the reduced dimensionality specified data to correspond to a lowest level of a hierarchy of reduced dimensionality clusters, using stored dimensionality reduction information; searching for candidate terminal clusters that can contain one or more of k nearest neighbors of the reduced dimensionality specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and for each candidate terminal cluster, performing an intra-cluster search for the k nearest neighbors to the reduced dimensionality specified data.

Claim 21

The method of claim 1, wherein the data is stored in a database, further comprising the steps of: reducing a dimensionality of the database and generating dimensionality reduction information associated with the database; and storing the dimensionality reduction information associated with the database; wherein said partitioning step is responsive to said reducing step.

Claim 22

The method of claim 20, for performing an exact search, comprising the steps of: reducing the dimensionality of specified data, based on the dimensionality reduction information for the database; associating reduced dimensionality specified data to one of the clusters, based on the clustering information, in response to said reducing; reducing a dimensionality of reduced dimensionality specified data to that of a reduced dimensionality cluster defined by an associated cluster, based on dimensionality reduction information for the associated cluster; and searching for a matching reduced dimensionality cluster, based on a reduced dimensionality version the specified data.

Claim 23

The method of claim 20, for performing a similarity search, comprising the steps of: reducing the dimensionality of specified data using the dimensionality reduction information associated with the database; finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; assessing whether other clusters can contain records closer to the specified data than the farthest of the k records retrieved; searching a closest other cluster to the specified data, in response to said assessing step; and repeating said assessing and searching for all said other clusters.

Claim 24

The method of claim 20, wherein the data is stored in a database further comprising the step of: generating and storing one or more reduced dimensionality searchable indexes for said one or more reduced dimensionality clusters.

Claim 25

The method of claim 20, for performing an exact search, comprising the steps of: associating specified data to one of the clusters based on stored clustering information; decomposing the specified data into a reduced dimensionality cluster defined by an associated cluster and stored dimensionality reduction information for the associated cluster, in response to said associating; and searching for a matching reduced dimensionality cluster based on decomposed specified data.

Claim 26

The method of claim 24, wherein the specified data includes a search template, further comprising the steps of: said associating comprising identifying the search template with a cluster based on the stored clustering information; said decomposing comprising projecting the search template onto a subspace for an identified cluster based on the stored dimensionality reduction information; and said searching comprising performing an intra-cluster search for a projected template.

Claim 27

A program storage device readable by a machine which includes one or more reduced dimensionality indexes to multidimensional data, the program storage device tangibly embodying a program of instructions executable by the machine to perform method steps for representing multidimensional data, said method steps comprising: a) partitioning the multidimensional data into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; and d) storing the dimensionality reduction information; e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 28

A program storage device readable by a machine which includes one or more reduced dimensionality indexes to multidimensional data, the program storage device tangibly embodying a program of instructions executable by the machine to perform method steps for representing multidimensional data, said method steps comprising: a) partitioning the multidimensional data into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; and d) storing the dimensionality reduction information; e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 29

The program storage device of claim 26, for performing an exact search, comprising the steps of: associating specified data to one of the clusters based on stored clustering information; decomposing the specified data into a reduced dimensionality cluster defined by an associated cluster and stored dimensionality reduction information for the associated cluster, in response to said associating; and searching said indexes for a matching reduced dimensionality cluster based on decomposed specified data.

Claim 30

The program storage device of claim 27, wherein the query includes a search template, further comprising the steps of: said associating comprising identifying the search template with a cluster based on the stored clustering information; said decomposing comprising projecting the search template onto a subspace for an identified cluster based on the stored dimensionality reduction information; and said searching comprising performing an intra-cluster search for a projected template.

Claim 31

The program storage device of claim 26, further comprising the steps of: (a) generating cluster boundaries, which correspond to a zeroth-order approximation to a geometry of said clusters; (b) approximating the geometry of each of the clusters by means of a minimum bounding box and generating a first-order approximation to the geometry of each cluster; (c) partitioning the bounding box into 2 k hyper rectangles, wherein said partitioning is at a midpoint of each dimension; (d) retaining only those hyper rectangles that contain data points and generating a second-order approximation to the geometry of the cluster; and (e) repeating said steps (c) and (d) for each retained hyper rectangle to generate successively the third-, fourth-, . . . , n-th approximations to the geometry of the cluster.

Claim 32

The program storage device of claim 26 wherein the data is stored in one of a spatial database or a multimedia database which includes a plurality of data records each containing a plurality of fields, further comprising the steps of: creating a representation of the database to be indexed as a set of vectors, where each vector corresponds to a row in the database and the elements of each vector correspond to the values, for a particular row, contained in the columns for which the searchable index will be generated; and said partitioning comprising partitioning the vectors into said one or more clusters.

Claim 33

The program storage device of claim 28, further comprising the step of storing the index entirely in the main memory of a computer.

Claim 34

The method of claim 26, wherein said generating a reduced dimensionality cluster comprises a singular value decomposition further comprising the steps of: producing a transformation matrix and eigenvalues of the transformation matrix for said each cluster; and selecting a subset of the eigenvalues including the largest eigenvalues; wherein the dimensionality reduction information includes the transformation matrix and the subset of the eigenvalues.

Claim 35

The program storage device of claim 32, for searching for k most similar records to specified data using the reduced dimensionality index, comprising the steps of: associating specified data to said one or more clusters, based on stored clustering information; projecting the specified data onto a subspace for an associated cluster based on stored dimensionality reduction information for the associated cluster; generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting; searching, via the index, for the associated cluster having k most similar records to the projected specified data; determining if any other associated cluster can include any of k most similar records to the projected specified data; and repeating said searching on said any cluster that can include any of the k most similar records to the specified data.

Claim 36

The program storage device of claim 33, wherein said searching, via the index, for the associated cluster, further comprises the step of: computing the distances (D) between k nearest neighbors in the associated cluster and the projected specified data as a function of a mismatch index δ 2 wherein, δ.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ∥orthogonal.sub.-- complement∥.sup.2. 35.

Claim 37

The program storage device of claim 33, wherein the specified data includes a search template, further comprising the steps of: said projecting step further comprising the step of projecting the template, using the dimensionality reduction information, onto a subspace associated with the cluster to which it belongs; generating template dimensionality reduction information for a projected template; wherein said searching, via the index is based on the projected template and the template dimensionality reduction information; and updating a set of the k most similar records to the search template.

Claim 38

The program storage device of claim 32, wherein said selecting a subset of the eigenvalues is a function of a precision and a recall of returned results.

Claim 39

The program storage device of claim 26, for searching for k records most similar to specified data, the method for searching comprising the steps of: identifying a cluster to which specified data belongs, based on the clustering information; reducing the dimensionality of the specified data based on the dimensionality reduction information for an identified cluster; generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; searching the multidimensional index, using the dimensionality reduction information, for a reduced-dimensionality version of the cluster to which the specified data belongs; retrieving via the multidimensional index, the k most similar records in the cluster; identifying other candidate clusters which can contain records closer to the specified data than the farthest of the k most similar records retrieved; searching a closest other candidate cluster to the specified data, in response to said determining step; and repeating said identifying and searching steps for all said other candidate clusters.

Claim 40

The program storage device of claim 37, further comprising the step of: computing the distances (D) between k nearest neighbors in the version of the cluster and the projected specified data as a function of a mismatch index δ 2 wherein, δ.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ∥orthogonal.sub.-- complement∥.sup.2. 39.

Claim 41

The program storage device of claim 26, wherein the clustering information includes information on a centroid of said one or more clusters, further comprising the step of associating the centroid with a unique label.

Claim 42

The program storage device of claim 26, wherein the dimensionality of the data is >8.

Claim 43

The program storage device of claim 26, for performing an exact search, comprising the steps of: associating specified data to one of the clusters based on stored clustering information; reducing the dimensionality of the specified data based on stored dimensionality reduction information for a reduced dimensionality version of a cluster, in response to said associating step; and searching, based on reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

Claim 44

The program storage device of claim 41, wherein said searching further comprises the step of conducting a linear scan to match the specified data.

Claim 45

The program storage device of claim 29, for searching a hierarchy of approximations to the geometric structure of each cluster, further comprising the steps of: reducing the dimensionality of the specified data using the dimensionality reduction information associated with the database; finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; assessing whether one or more other clusters can contain records closer to the specified data than the farthest of the k records retrieved; retaining an other cluster only if it can contain any of k-nearest neighbors of specified data based on boundaries of the cluster; iteratively determining if a retained cluster could contain any of the k-nearest neighbors, based on increasingly finer approximations to the geometry, and retaining the retained cluster only if the cluster is accepted at the finest level of the hierarchy of successive approximations; and identifying a retained cluster as a candidate cluster containing one or more of the k-nearest neighbors of the data, in response to said step of iteratively determining.

Claim 46

The program storage device of claim 26, for performing an exact search, comprising the steps of: recursively applying the steps of: finding a cluster to which specified data belongs, using stored clustering information; and reducing the dimensionality of the specified data using stored dimensionality reduction information, until a corresponding lowest level of the hierarchy of reduced dimensionality clusters has been reached; and searching, using the low dimensional indexes, for a reduced dimensionality version of the cluster matching the specified data.

Claim 47

The program storage device of claim 26, for performing a similarity search, further comprising the steps of: recursively applying the steps of: finding the cluster to which specified data belongs, using stored clustering information; and reducing the dimensionality of the specified data to correspond to the lowest level of the hierarchy of reduced dimensionality clusters, using stored dimensionality reduction information; searching for candidate terminal clusters that can contain one or more of k nearest neighbors of the specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and for each candidate terminal cluster, performing an intra-cluster search for the k nearest neighbors to the specified data.

Claim 48

The program storage device of claim 26, for performing a similarity search, further comprising the steps of: reducing the dimensionality of the specified data; recursively applying the steps of: finding the cluster to which reduced dimensionality specified data belongs, using stored clustering information; and reducing the dimensionality of the reduced dimensionality specified data to correspond to a lowest level of a hierarchy of reduced dimensionality clusters, using stored dimensionality reduction information; searching for candidate terminal clusters that can contain one or more of k nearest neighbors of the reduced dimensionality specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and for each candidate terminal cluster, performing an intra-cluster search for the k nearest neighbors to the reduced dimensionality specified data.

Claim 49

The program storage device of claim 26, wherein the data is stored in a database, further comprising the steps of: reducing a dimensionality of the database and generating dimensionality reduction information associated with the database; and storing the dimensionality reduction information associated with the database; wherein said partitioning step is responsive to said reducing step.

Claim 50

The program storage device of claim 47, for performing an exact search, comprising the steps of: reducing the dimensionality of specified data, based on the dimensionality reduction information for the database; associating reduced dimensionality specified data to one of the clusters, based on the clustering information, in response to said reducing; reducing a dimensionality of the specified data to that of a reduced dimensionality cluster defined by an associated cluster, based on dimensionality reduction information for the associated cluster; and searching for a matching reduced dimensionality cluster, based on a reduced dimensionality version the specified data.

Claim 51

The program storage device of claim 47, for performing a similarity search, comprising the steps of: reducing the dimensionality of specified data using the dimensionality reduction information associated with the database; finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; assessing whether other clusters can contain records closer to the specified data than the farthest of the k records retrieved; searching a closest other cluster to the specified data, in response to said assessing step; and repeating said assessing and searching for all said other clusters.

Claim 52

The program storage device of claim 47, wherein the data is stored in a database, further comprising the step of: generating and storing one or more reduced dimensionality searchable indexes for said one or more reduced dimensionality clusters.

Claim 53

A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for representing multidimensional data, the computer readable program code means in said computer program product comprising: computer readable program code clustering means for causing a computer to effect (a) partitioning the multidimensional data into one or more clusters; computer readable program code means, coupled to said clustering means, for causing a computer to effect (b) generating and storing clustering information for said one or more clusters; computer readable program code dimensionality reduction means, coupled to said clustering means, for causing a computer to effect, (c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; computer readable program code means, coupled to said dimensionality reduction means, for causing a computer to (d) effect storing the dimensionality reduction information; computer readable program code means for causing a computer to effect creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and computer readable program code means for causing a computer to effect generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 54

A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for representing multidimensional data, the computer readable program code means in said computer program product comprising: computer readable program code clustering means for causing a computer to effect (a) partitioning the multidimensional data into one or more clusters; computer readable program code means, coupled to said clustering means, for causing a computer to effect (b) generating and storing clustering information for said one or more clusters; computer readable program code dimensionality reduction means, coupled to said clustering means, for causing a computer to effect, (c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; computer readable program code means, coupled to said dimensionality reduction means, for causing a computer to (d) effect storing the dimensionality reduction information; computer readable program code means for causing a computer to effect creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and computer readable program code means for causing a computer to effect generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 55

A computerized method of representing multidimensional data which includes spatial geographic information, said method comprising the steps of: a) partitioning the spatial geographic information into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; d) storing the dimensionality reduction information; e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 56

A computerized method of representing multidimensional data which includes spatial geographic information, said method comprising the steps of: a) partitioning the spatial geographic information into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; d) storing the dimensionality reduction information; e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

Claim 57

The method of claim 52, wherein the geographic information includes image data, further comprising the steps of: extracting a set of features from the image data, wherein the features include one or more of: a texture; a shape; a contour; and a color histogram.

Claim 58

The computer program product of claim 51, further comprising: (a) means for causing a computer to effect generating cluster boundaries, which correspond to a zeroth-order approximation to a geometry of said clusters; (b) means for causing a computer to effect approximating the geometry of each of the clusters by means of a minimum bounding box and generating a first-order approximation to the geometry of each cluster; (c) means for causing a computer to effect partitioning the bounding box into 2 k hyper rectangles, wherein said partitioning is at a midpoint of each dimension; (d) means for causing a computer to effect retaining only those hyper rectangles that contain data points and generating a second-order approximation to the geometry of the cluster; and (e) means for causing a computer to effect repeating said steps (c) and (d) for each retained hyper rectangle to generate successively the third-, fourth-, . . . , n-th approximations to the geometry of the cluster.

Claim 59

The computer program product of claim 54, for searching a hierarchy of approximations to the geometric structure of each cluster, further comprising: means for causing a computer to effect reducing the dimensionality of the specified data using the dimensionality reduction information associated with the database; means for causing a computer to effect finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; means for causing a computer to effect reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; means for causing a computer to effect searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; means for causing a computer to effect retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; means for causing a computer to effect assessing whether one or more other clusters can contain records closer to the specified data than the farthest of the k records retrieved; means for causing a computer to effect retaining an other cluster only if it can contain any of k-nearest neighbors of specified data based on boundaries of the cluster; means for causing a computer to effect iteratively determining if a retained cluster could contain any of the k-nearest neighbors, based on increasingly finer approximations to the geometry, and retaining the retained cluster only if the cluster is accepted at the finest level of the hierarchy of successive approximations; and means for causing a computer to effect identifying a retained cluster as a candidate cluster containing one or more of the k-nearest neighbors of the data, in response to said step of iteratively determining.

Claim 60

The computer program product of claim 51 wherein the data is stored in one of a spatial database or a multimedia database which includes a plurality of data records each containing a plurality of fields, further comprising: computer readable program code means for causing a computer to effect creating a representation of the database to be indexed as a set of vectors, where each vector corresponds to a row in the database and the elements of each vector correspond to the values, for a particular row, contained in the columns for which the searchable index will be generated; and said clustering means comprising computer readable program code means for causing a computer to effect partitioning the vectors into said one or more clusters.

Claim 61

The computer program product of claim 51, wherein said generating a reduced dimensionality cluster comprises a singular value decomposition further comprising: computer readable program code means for causing a computer to effect producing a transformation matrix and eigenvalues of the transformation matrix for said each cluster; and computer readable program code means for causing a computer to effect selecting a subset of the eigenvalues including the largest eigenvalues; wherein the dimensionality reduction information includes the transformation matrix and the subset of the eigenvalues.

Claim 62

The computer program product of claim 57, for searching for k most similar records to specified data using the reduced dimensionality index, comprising: computer readable program code means for causing a computer to effect associating specified data to said one or more clusters, based on stored clustering information; computer readable program code means for causing a computer to effect projecting the specified data onto a subspace for an associated cluster based on stored dimensionality reduction information for the associated cluster; computer readable program code means for causing a computer to effect generating dimensionality reduction information including an orthogonal complement for projected specified data; means for causing a computer to effect searching, via the index, for the associated cluster having k most similar records to the projected specified data; means for causing a computer to effect determining if any other associated cluster can include any of k most similar records to the projected specified data; and means for causing a computer to effect repeating said searching on said any cluster that can include any of the k most similar records to the specified data.

Claim 63

The computer program product of claim 58, wherein said means for causing a computer to effect searching, via the index, for the associated cluster further comprises: means for causing a computer to effect computing distances (D) between k nearest neighbors in the associated cluster and the projected specified data as a function of a mismatch index δ 2 wherein, δ.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ∥orthogonal.sub.-- complement∥.sup.2. 60.

Claim 64

The computer program product of claim 58, wherein the specified data includes a search template, further comprising: said means for causing a computer to effect projecting including means for causing a computer to effect projecting the template, using the dimensionality reduction information, onto a subspace associated with the cluster to which it belongs; means for causing a computer to effect generating template dimensionality reduction information for a projected template; wherein said means for causing a computer to effect searching, via the index is based on the projected template and the template dimensionality reduction information; and means for causing a computer to effect updating a set of the k most similar records to the search template.

Claim 65

The computer program product of claim 57, wherein said means for causing a computer to effect selecting a subset of the eigenvalues is a function of a precision and a recall of returned results.

Claim 66

The computer program product of claim 51, for searching for k records most similar to specified data, the method for searching comprising: means for causing a computer to effect identifying a cluster to which specified data belongs, based on the clustering information; means for causing a computer to effect reducing the dimensionality of the specified data based on the dimensionality reduction information for an identified cluster; means for causing a computer to effect generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; means for causing a computer to effect searching the multidimensional index, using the dimensionality reduction information, for a reduced-dimensionality version of the cluster to which the specified data belongs; means for causing a computer to effect retrieving via the multidimensional index, the k most similar records in the cluster; means for causing a computer to effect identifying other candidate clusters which can contain records closer to the specified data than the farthest of the k most similar records retrieved; means for causing a computer to effect searching a closest other candidate cluster to the specified data, in response to said identifying step; and means for causing a computer to effect repeating said identifying and searching steps for all said other candidate clusters.

Claim 67

The computer program product of claim 51, for performing an exact search, comprising: means for causing a computer to effect associating specified data to one of the clusters based on stored clustering information; means for causing a computer to effect reducing the dimensionality of the specified data based on stored dimensionality reduction information for a reduced dimensionality version of a cluster, in response to said associating step; and means for causing a computer to effect searching, based on reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

Claim 68

The computer program product of claim 63, wherein said searching further comprises means for causing a computer to effect a linear scan to match the specified data.

Claim 69

A computerized method of representing multidimensional data which includes point-of-sale transactions with associated geographic coordinates, said method comprising the steps of: a) partitioning the point-of-sales transactions into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; and d) storing the dimensionality reduction information.

Claim 70

A computerized method of representing multidimensional data which includes point-of-sale transactions with associated geographic coordinates, said method comprising the steps of: a) partitioning the point-of-sales transactions into one or more clusters; b) generating and storing clustering information for said one or more clusters; c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; and d) storing the dimensionality reduction information.

Claim 71

The computer program product of claim 51, for performing an exact search, comprising: means for causing a computer to effect recursively applying: means for causing a computer to effect finding a cluster to which specified data belongs, using stored clustering information; and means for causing a computer to effect reducing the dimensionality of the specified data using stored dimensionality reduction information, until a corresponding lowest level of the hierarchy of reduced dimensionality clusters has been reached; and means for causing a computer to effect searching, using the low dimensional indexes, for a reduced dimensionality version of the cluster matching the specified data.

Claim 72

The computer program product of claim 51, for performing a similarity search, further comprising: means for causing a computer to effect reducing the dimensionality of the specified data; means for causing a computer to effect recursively applying: means for causing a computer to effect finding the cluster to which reduced dimensionality specified data belongs, using stored clustering information; and means for causing a computer to effect reducing the dimensionality of the reduced dimensionality specified data to correspond to a lowest level of a hierarchy of reduced dimensionality clusters, using stored dimensionality reduction information; means for causing a computer to effect searching for candidate terminal clusters that can contain one or more of k nearest neighbors of the reduced dimensionality specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and means for causing a computer to effect for each candidate terminal cluster, performing an intra-cluster search for the k nearest neighbors to the reduced dimensionality specified data.

Claim 73

The computer program product of claim 51, wherein the data is stored in a database, further comprising: means for causing a computer to effect reducing a dimensionality of the database and generating dimensionality reduction information associated with the database; and means for causing a computer to effect storing the dimensionality reduction information associated with the database; wherein said partitioning step is responsive to said reducing step.

Claim 74

The computer program product of claim 68, for performing an exact search, comprising: means for causing a computer to effect reducing the dimensionality of specified data, based on the dimensionality reduction information for the database; means for causing a computer to effect associating reduced dimensionality specified data to one of the clusters, based on the clustering information, in response to said reducing; means for causing a computer to effect reducing a dimensionality of reduced dimensionality specified data to that of a reduced dimensionality cluster defined by an associated cluster, based on dimensionality reduction information for the associated cluster; and means for causing a computer to effect searching for a matching reduced dimensionality cluster, based on a reduced dimensionality version the specified data.

Claim 75

The computer program product of claim 68, for performing a similarity search, comprising: means for causing a computer to effect reducing the dimensionality of specified data using the dimensionality reduction information associated with the database; means for causing a computer to effect finding the cluster to which reduced dimensionality specified data belongs, based on the clustering information; means for causing a computer to effect reducing the dimensionality of the reduced dimensionality specified data based on the dimensionality reduction information for an identified cluster; means for causing a computer to effect searching for a reduced-dimensionality version of the cluster to which the further reduced dimensionality specified data belongs; means for causing a computer to effect retrieving via the multidimensional index, k records most similar to the further reduced dimensionality specified data in the cluster; means for causing a computer to effect assessing whether other clusters can contain records closer to the specified data than the farthest of the k records retrieved; means for causing a computer to effect searching a closest other cluster to the specified data, in response to said assessing step; and means for causing a computer to effect repeating said assessing and searching for all said other clusters.

Claim 76

The computer program product of claim 68, wherein the data is stored in a database, further comprising: means for causing a computer to effect generating and storing one or more reduced dimensionality searchable indexes for said one or more reduced dimensionality clusters.

Claim 77

The computer program product of claim 68, for performing an exact search, comprising: means for causing a computer to effect associating specified data to one of the clusters based on stored clustering information; means for causing a computer to effect decomposing the specified data into a reduced dimensionality cluster defined by an associated cluster and stored dimensionality reduction information for the associated cluster, in response to said associating; and means for causing a computer to effect searching for a matching reduced dimensionality cluster based on decomposed specified data.

Claim 78

The computer program product of claim 72, wherein the query includes a search template, further comprising: means for causing a computer to effect said associating comprising identifying the search template with a cluster based on the stored clustering information; said means for causing a computer to effect decomposing comprising means for causing a computer to effect projecting the search template onto a subspace for an identified cluster based on the stored dimensionality reduction information; and said means for causing a computer to effect searching comprising means for causing a computer to effect performing an intra-cluster search for a projected template.