Searching multidimensional indexes using associated clustering and dimension reduction information

• US 6,134,541 A
• Filed: 10/31/1997
• Issued: 10/17/2000
• Est. Priority Date: 10/31/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Castelli, Vittorio, Li, Chung-Sheng, Thomasian, Alexander
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LE, UYEN T
• Application Number:
  US08/961,729
• Time in Patent Office: 1,082 Days
• Field of Search: 707/2, 707/3, 707/1, 395/601, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index 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/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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 also can be applied to the entire database as a first step of the index generation.

Claims

1. In a system including one or more reduced dimensionality indexes to multidimensional data, a method for performing an exact search for specified data using the one or more indexes, the method comprising the following steps in the sequence set forth:

associating specified data to a data cluster based on clustering information, said data cluster being a partition of an original data input set;

reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of the cluster;

recursively applying said associating and reducing steps unitl a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and

searching, using low dimensional indexes to said lowest level and a reduced dimensionality specified data, for cluster elements of the reduced dimensionality version of the cluster matching the specified data.

3. The method of claim 1, wherein said reducing step comprises a singular value decomposition, said searching further comprising the step of:

searching an index for a matching reduced dimensionality cluster, based on decomposed specified data.

4. The method of claim 3, wherein the specified data includes a search template, further comprising the steps of:

said associating comprising identifying the search template with the cluster, based on the clustering information;

said singular value decomposition comprising projecting the search template onto a subspace for an identified cluster, based on the dimensionality reduction information; and

said searching comprising performing an intra-cluster search for a projected template.

5. The method of claim 3, wherein the dimensionality reduction information comprises a transformation matrix and selected eigenvalues of the transformation matrix.

6. The method of claim 1, further comprising the steps of:

reducing the dimensionality of specified data, based on dimensionality reduction information for the database;

wherein said associating step is in response to said reducing the dimensionality of specified data, based on dimensionality reduction information for the database.

8. The method of claim 1, wherein the clustering information comprises an identifier of a centroid of the cluster associated with a unique label.

2. A method for performing an exact search for specified data, comprising the following steps in the sequence set forth:

associating specified data to a data cluster based on clustering information, said data cluster being a partition from an original data input set;

reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of the cluster;

recursively applying said associating and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and

linearly scanning, based on a reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

7. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing an exact search for specified data, said method comprising:

associating specified data to a data cluster based on clustering information, said data cluster being a partition of an original data input set;

after said associating, reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of the cluster;

recursively applying said associating and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and

linearly scanning, based on a reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

9. In a system including one or more reduced dimensionality indexes to multidimensional data, a method for searching for k records most similar to specified data, using the one or more indexes, the method comprising the steps of:

identifying the specified data with a cluster based on clustering information, said cluster being a partition from an original data input set;

after said identifying step, reducing a dimensionality of the specified data, based on dimensionality reduction information for an identified cluster;

recursively applying said identifying and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached;

generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; and

retrieving the ≦

k records most similar to the specified data from the identified cluster using the one or more reduced dimensionality indexes, the dimensionality reduction information and the reduced dimensionality specified data.

10. The method of claim 9, further comprising the steps of:

identifying one or more other candidate clusters which can contain records closer to the specified data than the farthest of the k records retrieved;

searching a closest other candidate cluster to the specified data, in response to said identifying step; and

repeating said identifying and searching for all said other candidate clusters.

11. The method of claim 9, wherein the specified data includes a search, template, the method further comprising the steps of:

said reducing comprising projecting the specified data onto a subspace for an associated cluster, based on dimensionality reduction information for the identified cluster; and

generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting.

12. The method of claim 11, wherein said retrieving includes a nearest neighbor search, further comprising the steps of:

searching the identified cluster for the k nearest neighbors to the projected specified data;

determining if any other associated clusters can include any of k nearest neighbors to the projected specified data; and

repeating said searching on said any clusters that can include any of the k nearest neighbors.

13. The method of claim 12, wherein said retrieving further comprises the step of:

computing the distances (D) between the k nearest neighbors in the identified cluster and the reduced dimensionality specified data as a function of an element index δ

² where

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

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

∥

orthogonal.sub.-- complement∥

.sup.2.

14. The method of claim 13, further comprising the step of updating a k nearest neighbor set when an element is found having the index δ

² value less than a largest index δ

² currently in the k nearest neighbor set, in response to said determining.

15. The method of claim 11, further comprising the steps of:

wherein said projecting step produces a projected template and template dimensionality reduction information; and

wherein said searching, via the index is based on the projected template and the template dimensionality reduction information; and

updating a k-nearest neighbor set of the k records most similar to the search template.

16. The method of claim 9, further comprising the steps of:

reducing the dimensionality of the specified data, based on dimensionality reduction information for a database;

wherein said identifying step is responsive to said reducing the dimensionality of specified data, based on dimensionality reduction information for the database.

17. The method of claim 9, further comprising the steps of:

searching for candidate terminal clusters that can contain one or more of the k records most similar to 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 records most similar to the specified data.

18. The method of claim 9, wherein the records retrieved is a function of a precision and a recall.

19. The method of claim 18, further comprising the step of specifying a desired precision of a search and lower bound on an allowed recall;

and said reducing comprising the step of deriving a maximum value of precision for which the allowed recall can be attained.

20. The method of claim 18, further comprising the step of specifying a value of desired recall;

and said reducing comprising the step of estimating a cost of increasing the precision to attain the desired recall;

wherein a number of reduced dimensionality indexes minimizes the cost of a search based on the value of desired recall.

21. 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 performing an exact search for specified data using the one or more indexes, said method steps comprising:

associating specified data to a data cluster based on clustering information, said data cluster being a partition of an original data input set;

reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of the cluster;

recursively applying said associating and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and

searching, using low dimensional indexes to said lowest level and a reduced dimensionality specified data, for cluster elements of the reduced dimensionality version of the cluster matching the specified data.

22. The program storage device of claim 21, wherein the clustering information comprises an identifier of a centroid of the cluster associated with a unique label.

23. The program storage device of claim 21, wherein said reducing step comprises a singular value decomposition, said searching further comprising the step of:

searching an index for a matching reduced dimensionality cluster, based on decomposed specified data.

24. The program storage device of claim 23, wherein the specified data includes a search template, further comprising the steps of:

said associating comprising identifying the search template with the cluster, based on the clustering information;

said singular value decomposition comprising projecting the search template onto a subspace for an identified cluster, based on the dimensionality reduction information; and

said searching comprising performing an intra-cluster search for a projected template.

25. The program storage device of claim 23, wherein the dimensionality reduction information comprises a transformation matrix and selected eigenvalues of the transformation matrix.

26. The program storage device of claim 21, further comprising the steps of:

reducing the dimensionality of specified data, based on dimensionality reduction information for the database;

wherein said associating step is in response to said reducing the dimensionality of specified data, based on dimensionality reduction information for the database.

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 searching for k records most similar to specified data, using the one or more indexes, said method steps comprising:

identifying the specified data with a data cluster based on clustering information, said data cluster being a partition of an original data input set;

after said identifying step, reducing a dimensionality of the specified data, based on dimensionality reduction information for an identified cluster;

recursively applying said identifying and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached;

generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; and

retrieving the ≦

k records most similar to the specified data, from the identified cluster using the one or more reduced dimensionality indexes, the dimensionality reduction information and the reduced dimensionality specified data.

30. The program storage device of claim 27, further comprising the steps of:

identifying one or more other candidate clusters which can contain records closer to the specified data than the farthest of the k records retrieved;

searching a closest other candidate cluster to the specified data, in response to said determining step; and

repeating said identifying and searching for all said other candidate clusters.

31. The program storage device of claim 27, wherein the specified data includes a search template, farther comprising the steps of:

said reducing comprising projecting the specified data onto a subspace for an associated cluster, based on dimensionality reduction information for the identified cluster; and

generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting.

32. The program storage device of claim 31, wherein said retrieving includes a nearest neighbor search, further comprising the steps of:

searching the identified cluster for the k nearest neighbors to the projected specified data;

determining if any other associated clusters can include any of k nearest neighbors to the projected specified data; and

repeating said searching on said any clusters that can include any of the k nearest neighbors.

33. The program storage device of claim 32, wherein said retrieving further comprises the step of:

computing the distances (D) between the k nearest neighbors in the identified cluster and the reduced dimensionality specified data as a function of an element index δ

² where

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

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

∥

orthogonal.sub.-- complement∥

.sup.2.

34.

34. The program storage device of claim 33, further comprising the step of updating a k nearest neighbor set when an element is found having the index δ

² value less than a largest index δ

² currently in the k nearest neighbor set, in response to said determining.

35. The program storage device of claim 31, further comprising the steps of:

wherein said projecting step produces a projected template and template dimensionality reduction information; and

wherein said retrieving, using the index is based on the projected template and the template dimensionality reduction information; and

updating a k-nearest neighbor set of the k records most similar to the search template.

38. The program storage device of claim 27, wherein the records retrieved are a function of a precision and a recall.

39. The program storage device of claim 38, further comprising the step of specifying a desired precision of a search and lower bound on an allowed recall;

and said reducing comprising the step of deriving a maximum value of precision for which the allowed recall can be attained.

40. The program storage device of claim 38, further comprising the step of specifying a value of desired recall;

and said reducing comprising the step of estimating a cost of increasing the precision to attain the desired recall;

wherein a number of reduced dimensionality indexes minimizes the cost of a search based on the value of desired recall.

28. A computer program product comprising:

a computer usable medium having computer readable program code means embodied therein for searching for k records most similar to a search template, using one or more multidimensional indexes, the computer readable program code means in said computer program product comprising;

computer readable program code cluster search means for identifying the search template with a cluster based on clustering information, said cluster being a partition of an original data input set;

computer readable program code template projection means for reducing a dimensionality of the search template, after said identifying, based on dimensionality reduction information for an identified cluster;

computer readable program code means for causing the computer to recursively apply said cluster search means and said template projection means until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached;

computer readable program code means for generating dimensionality reduction information for a reduced dimensionality search template, in response to said reducing; and

computer readable program code intra-cluster search means for retrieving the ≦

k records most similar to the specified data from the identified cluster using the one or more reduced dimensionality indexes, the dimensionality reduction information and the reduced dimensionality specified data.

29. The computer program product of claim 28, further comprising computer readable program code means for causing the computer to recursively effect:

identifying one or more other candidate clusters which can contain records closer to the specified data than the farthest of the k records retrieved; and

searching a closest other candidate cluster to the specified data.

36. The program storage device of claim 29, further comprising the steps of:

reducing the dimensionality of the specified data, based on dimensionality reduction information for a database;

wherein said identifying step is responsive to said reducing the dimensionality of specified data, based on dimensionality reduction information for the database.

37. The program storage device of claim 29, further comprising the steps of:

searching for candidate terminal clusters that can contain one or more of the k records most similar to 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 records most similar to the specified data.

45. The computer program product of claim 28, wherein said cluster search means for causing a computer to effect associating specified data to a reduced dimensionality cluster further comprises:

computer readable program code cluster search means for causing a computer to effect adapting to the local structure of data.

46. The computer program product of claim 29, wherein said computer readable program code means for causing the computer to recursively effect:

identifying one or more other candidate clusters which can contain records closer to the specified data than the farthest of the k records retrieved, further comprises;

computer readable program code means for causing the computer to identify said other candidate clusters that can contain elements closer than a prescribed distance from a data point, using a hierarchy of successive approximations to the geometry of the clusters.

47. The computer program product of claim 46, wherein said computer readable program code means for causing the computer to identify said other candidate clusters that can contain elements closer than a prescribed distance from a data point, using a hierarchy of successive approximations to the geometry of the clusters, further comprises:

(a) computer readable program code means for causing the computer to retain the cluster only if it can contain any of k-nearest neighbors of specified data, based on a cluster boundaries;

(b) computer readable program code means for causing the computer to iteratively determine 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

(c) computer readable program code means for causing the computer to identify a retained cluster as a candidate cluster containing one or more of the k-nearest neighbors of the data.

48. The computer program product of claim 46, wherein said intra-cluster search logic further comprises computer readable program code nearest neighbor search means for causing the computer to compute the distances (D) between k nearest neighbors in the identified cluster and the reduced dimensionality search template as a function of an element index δ

³ where

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

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

∥

orthogonal.sub.-- complement∥

.sup.2.

49. The computer program product of claim 46, wherein said template projection means comprises computer readable program code means to cause the computer to produce a projected template and template dimensionality reduction information;

and wherein said intra-cluster logic means is based on the projected template and the template dimensionality reduction information; and

computer readable program code means for causing the computer to update a k-nearest neighbor set of the k records most similar to the search template.

50. The computer program product of claim 46, further comprising computer readable program code means for causing the computer to effect reducing the dimensionality of the search template, based on dimensionality reduction information for a database;

wherein said cluster search means is coupled to said means for causing the computer to effect reducing the dimensionality of the search template, based en dimensionality reduction information for the database.

51. The computer program product of claim 28, further comprising:

computer readable program code means for causing the computer to search for candidate terminal clusters that can contain one or more of the k records most similar to the search template 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 search template belongs; and

computer readable program code means for causing the computer to effect for each candidate terminal cluster, performing an intra-cluster search for the k records most similar to the search template.

41. 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 searching for k records most similar to specified data, using the one or more indexes, said method steps comprising:

identifying the specified data with a cluster based on clustering information, said cluster being a partition of an original data input set;

after the identifying step, reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of an identified cluster;

recursively applying said identifying and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached;

generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; and

linearly scanning, based on the reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.

42. A computer program product comprising:

a computer usable medium having computer readable program code means embodied therein for performing an exact search for a search template using one or more multidimensional indexes, the computer readable program code means in said computer program product comprising;

computer readable program code cluster search means for causing a computer to effect associating specified data to a data cluster based on clustering information, said data cluster being a partition of an original data input set;

computer readable program code template projection means for causing a computer to effect reducing a dimensionality of the search template, after said associating, based on dimensionality reduction information for a reduced dimensionality version of the cluster;

computer readable program code means for causing a computer to effect recursively applying said cluster search means and template projection means until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and

computer readable program code intra-cluster search means for causing a computer to effect searching, using low dimensional indexes to said lowest level and a reduced dimensionality search template, for cluster elements of the reduced dimensionality version of the cluster matching the search template.

43. The computer program product of claim 42, wherein said template projection means comprises a singular value decomposition means for causing a computer to effect projecting the search template onto a subspace for an identified cluster, based on the dimensionality reduction information.

44. The computer program product of claim 42, further comprising computer readable program code means for causing a computer to effect reducing the dimensionality of the search template, based on dimensionality reduction information for the database;

wherein said cluster search means is coupled to said means for causing a computer to effect reducing the dimensionality of the search template, based on dimensionality reduction information for the database.