System and method for similarity indexing and searching in high dimensional space

• US 6,922,700 B1
• Filed: 05/16/2000
• Issued: 07/26/2005
• Est. Priority Date: 05/16/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu Chandra, Yu, Philip Shi-lung
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US09/571,471
• Time in Patent Office: 1,897 Days
• Field of Search: 707 1- 10, 707100-1041, 707/200, 707/201, 707/205, 707/506, 707/530, 707/531, 702/127, 702179-181, 711/100, 711/170, 711/173, 715/500, 715/530, 715/531, 715/764, 715/853, 715/854, 345/418, 345/419, 345/764, 345/853, 345/854
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method for providing similarity indexing and searching in multi-dimensional databases. In one aspect, given a set of data points in a multidimensional space, the values of the data points on each dimension are partitioned into a plurality of grids, wherein each grid is assigned a grid value. Given a target data point, similarity candidates (i.e., data points that are similar to the target data point) are identified based on matching grid values. An inverted grid index comprising an index on the data points falling into each grid of each dimension is utilized to identify similarity candidates. A similarity selection process is employed to select the closest identified similarity candidates for output, which utilizes a similarity function to measure the closeness of each identified similarity candidate to the target data point. A preferred similarity function is one that considers a subset of the dimensions in which a point falls within a similar grid of the target point. In addition, a correlation effect among the grids in different dimensions may be a factor captured in the similarity function.

Claims

1. A method for managing a plurality of data points in a multi-dimensional space, the method comprising the steps of:

receiving a plurality of data points, wherein each data point comprises a multi-dimensional record comprising a value in at least one of the dimensions;

partitioning values of the data points in each dimension into a plurality of grids, wherein each grid is assigned a grid value or a range of grid values; and

identifying at least one data point in the plurality of data points that is similar to a target data point based on matching grid values.

2. The method of claim 1, wherein the step of identifying is based on matching grid values of a subset of the dimensions.

3. The method of claim 1, wherein at least one of the data points of the plurality of data points is not fully specified in each dimension.

4. The method of claim 1, wherein the step of partitioning comprises equi-depth partitioning.

5. The method of claim 4, wherein a high skew value is ignored for the equi-depth partitioning.

6. The method of claim 1, wherein the step of partitioning is based on the number of dimensions.

7. The method of claim 1, further comprising the step of indexing the plurality of data points to generate an index on data points falling within each dimension.

8. The method of claim 7, wherein the step of indexing comprises the step of indexing data points comprising each dimension to generate an index on data points falling within each grid of each dimension.

9. The method of claim 7, wherein the step of identifying is performed using the index.

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

computing a similarity score for each of the data points identified as being similar to the target data point; and

selecting for output the data points having a computed similarity score that meets a predefined selection criterion.

11. The method of claim 10, wherein the predefined selection criterion comprises one of a threshold value and u-best scores.

12. The method of claim 10, wherein the step of computing a similarity score comprises the step of considering a subset of the dimensions to compute the similarity score.

13. The method of claim 12, wherein the similarity score is additive over each dimension in the subset of dimensions.

14. The method of claim 12, wherein for a given dimension in the subset of dimensions, the similarity score is computed based on a grid range and a distance between the similar data point and the target point over the given dimension.

15. The method of claim 12, wherein the subset of dimensions comprises at least one dimension having a grid that comprises both the similar data point and the target data point.

16. The method of claim 12, wherein the subset of dimensions comprises as least one dimension having a first grid comprising the similar data point and a second grid comprising the target data point wherein a distance between the first and second grid falls within a predefined distance threshold.

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

generating correlation data representing a correlation between grids in different dimensions; and

utilizing the correlation data to compute the similarity scores.

18. The method of claim 17, wherein the step of utilizing the correlation data to compute the similarity scores comprises increasing a similarity score for a given data point by a predetermined amount based on the correlation data.

19. The method of claim 17, wherein the step of generating correlation data comprises the step of determining a correlation support count between each pair of grids in different dimensions.

20. The method of claim 19, where the correlation support count between a given pair of grids in different dimensions comprises the number of similar data points within the given pair of grids.

21. The method of claim 20, wherein the step of utilizing the correlation data to compute the similarity scores comprises utilizing correlation data associated with a strongly correlated pair of grids to compute the similarity score, wherein a strongly correlated pair of grids comprises a correlation support count that exceeds a predetermined correlation threshold.

22. The method of claim 1, wherein each data point comprises a document, wherein each dimension of each data point comprises a word in the corresponding document, wherein each value of each data point comprises an occurrence count of the corresponding word of the corresponding document, and wherein the method is employed to retrieve at least one document comprising content that is similar to a target document.

23. The method of claim 22, wherein the step of partitioning step considers positive grid values.

24. The method of claim 1, wherein each data point comprises a user, wherein each dimension of each data point comprises a product, wherein each value of each data point comprises a rating value for the corresponding product that is specified by the corresponding user, and wherein the method is employed to identify a user having similar product ratings of a target user.

25. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a plurality of data points in a multi-dimensional space, the method comprising the steps of:

receiving a plurality of data points, wherein each data point comprises a multi-dimensional record comprising a value in at least one of the dimensions;

partitioning values of the data points in each dimension into a plurality of grids, wherein each grid is assigned a grid value or a range of grid values; and

identifying at least one data point in the plurality of data points that is similar to a target data point based on matching grid values.

26. The program storage device of claim 25, wherein the instructions for identifying comprise instructions for matching grid values of a subset of the dimensions.

27. The program storage device of claim 25, further comprising instructions for performing the step of indexing the plurality of data points to generate an index on data points falling within each grid of each dimension, wherein the step of identifying is performed using the index.

28. The program storage device of claim 25, further comprising instructions for performing the steps of:

computing a similarity score for each of the data points identified as being similar to the target data point;

selecting for output the data points having a computed similarity score that meets a predefined selection criterion.

29. The program storage device of claim 28, wherein the at least on predefined selection criterion comprises one of a threshold value and u-best scores.

30. The program storage device of claim 28, wherein the instructions for performing the step of computing a similarity score comprise instructions for considering a subset of the dimensions to compute the similarity score.

31. The program storage device of claim 30, wherein the similarity score is additive over each dimension in the subset of dimensions.

32. The program storage device of claim 30, wherein for a given dimension in the subset of dimensions, the similarity score is computed based on a grid range and a distance between the similar data point and the target point over the given dimension.

33. The program storage device of claim 30, wherein the subset of dimensions comprises at least one dimension having a grid that comprises both the similar data point and the target data point.

34. The program storage device of claim 30, wherein the subset of dimensions comprises as least one dimension having a first grid comprising the similar data point and a second grid comprising the target data point wherein a distance between the first and second grid falls within a predefined distance threshold.

35. The program storage device of claim 28, further comprising instructions for performing the steps of:

generating correlation data representing a correlation between grids in different dimensions; and

utilizing the correlation data to compute the similarity scores.

36. The program storage device of claim 35, wherein the instructions for performing the step of utilizing the correlation data to compute the similarity scores comprise instructions for increasing a similarity score for a given data point by a predetermined amount based on the correlation data.

37. The program storage device of claim 35, wherein the instructions for performing the step of generating correlation data comprise instructions for performing the step of determining a correlation support count between each pair of grids in different dimensions.

38. The program storage device of claim 37, wherein the correlation support count between a given pair of grids in different dimensions comprises the number of similar data points within the given pair of grids.

39. The program storage device of claim 38, wherein the instructions for performing the step of utilizing the correlation data to compute the similarity scores comprise instructions for utilizing correlation data associated with a strongly correlated pair of grids to compute the similarity score, wherein a strongly correlated pair of grids comprises a correlation support count that exceeds a predetermined correlation threshold.

40. The program storage device of claim 25, wherein each data point comprises a document, wherein each dimension of each data point comprises a word in the corresponding document, wherein each value of each data point comprises an occurrence count of the corresponding word of the corresponding document, and wherein the method steps are employed to retrieve at least one document comprising content that is similar to a target document.

41. The program storage device of claim 25, wherein each data point comprises a user, wherein each dimension of each data point comprises a product, wherein each value of each data point comprises a rating value for the corresponding product that is specified by the corresponding user, and wherein the method steps are employed to identify a user having similar product ratings of a target user.

42. A system for managing a database having a plurality of dimensions, the system comprising:

a plurality of multi-dimensional objects stored in the database, wherein each multi-dimensional object comprises a value for at least one of the dimensions, and wherein each dimension of the database is partitioned into a plurality of grids based on object values in corresponding dimensions, wherein each grid is assigned a grid value or a range of grid values; and

a similarity search routine for identifying an object in the database that is similar to a target object based on matching grids.

43. The system of claim 42, wherein the similarity search routine considers a subset of the dimensions for identifying a similar object.

44. The system of claim 42, further comprising an index of objects falling within each dimension, wherein the index is utilized by the similarity search routing for identifying an object that is similar to the target object.

45. The system of claim 44, further comprising an index of objects falling within each grid of each dimension, wherein the index is utilized by the similarity search routine for identifying an object that is similar to the target object.

46. The system of claim 42, further comprising:

a similarity function for computing a similarity score for an object identified as being similar to the target data point, wherein the similarity search routine returns, as a search result, an object having a computed similarity score that meets a predefined selection criterion.

47. The system of claim 46, wherein the similarity function considers a value of each dimension of a subset of the dimensions of an object to compute the similarity score for the object.

48. The system of claim 46, further comprising a correlation table comprising correlation data representing a correlation between grids in different dimensions, wherein the similarity function utilizes the correlation data to compute the similarity scores.

49. The system of claim 42, wherein each object comprises a document, wherein each dimension of each object comprises a word in the corresponding document, wherein each value of each object comprises an occurrence count of the corresponding word of the corresponding document, and wherein the system comprises a document retrieval system for retrieving at least one document comprising content that is similar to a target document.

50. The system of claim 42, wherein each object comprises a user, wherein each dimension of each object comprises a product, wherein each value of each object comprises a rating value for the corresponding product that is specified by the corresponding user, and wherein the system comprises a collaborative filtering system for identifying a user having similar product ratings of a target user.