Multidimensional data clustering and dimension reduction for indexing and searching

• US 6,122,628 A
• Filed: 10/31/1997
• Issued: 09/19/2000
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thomasian, Alexander, Castelli, Vittorio, Li, Chung-Sheng
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): LE, UYEN T
• Application Number:
  US08/960,540
• Time in Patent Office: 1,054 Days
• Field of Search: 707/3, 707/2, 707/5, 707/1, 707/4, 707/101, 395/601, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An improved multidimensional data indexing technique that generates compact indexes such that most or all of the index can reside in main memory at any time. During the clustering and dimensionality reduction, clustering information and dimensionality reduction information are generated for use in a subsequent search phase. The indexing technique can be effective even in the presence of variables which are not highly correlated. Other features provide for efficiently performing exact and nearest neighbor searches using the clustering information and dimensionality reduction information. One example of the dimensionality reduction uses a singular value decomposition technique. The method can also be recursively applied to each of the reduced-dimensionality clusters. The dimensionality reduction can also be applied to the entire database as a first step of the index generation.

Claims

1. 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.

2. 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.

3. 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.

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

5. 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.

6. 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.

7. 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 δ

² wherein,

space="preserve" listing-type="equation">δ

.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ

∥

orthogonal.sub.-- complement∥

.sup.2.

8.

8. 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.

9. 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.

10. 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.

11. 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 δ

² wherein,

space="preserve" listing-type="equation">δ

.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ

∥

orthogonl.sub.-- complement∥

.sup.2.

12.

12. 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.

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

8.

14. 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.

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

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

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

32. 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.

33. 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.

34. 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 δ

² wherein,

space="preserve" listing-type="equation">δ

.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ

∥

orthogonal.sub.-- complement∥

.sup.2.

35.

35. 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.

36. 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.

37. 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.

38. 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 δ

² wherein,

space="preserve" listing-type="equation">δ

.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ

∥

orthogonal.sub.-- complement∥

.sup.2.

39.

39. 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.

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

8.

41. 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.

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

43. 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.

44. 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.

45. 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.

46. 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.

47. 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.

48. 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.

49. 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.

50. 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.

51. 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.

54. 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.

55. 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.

56. 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.

57. 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.

58. 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.

59. 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 δ

² wherein,

space="preserve" listing-type="equation">δ

.sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+Σ

∥

orthogonal.sub.-- complement∥

.sup.2.

60.

60. 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.

61. 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.

62. 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.

63. 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.

64. 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.

66. 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.

67. 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.

68. 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.

69. 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.

70. 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.

71. 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.

72. 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.

73. 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.

52. 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.

53. 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.

65. 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.