Methods and apparatus for indexing in a database and for retrieving data from a database in accordance with queries using example sets

• US 7,266,545 B2
• Filed: 08/07/2001
• Issued: 09/04/2007
• Est. Priority Date: 08/07/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Castelli, Vittorio, Li, Chung-Sheng, Bergman, Lawrence D.
• Primary Examiner(s): Breene; John
• Assistant Examiner(s): To; Baoquoc N.
• Application Number:
  US09/923,530
• Publication Number:
  US 20030033300A1
• Time in Patent Office: 2,219 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 707/104.1, 382/305, 382/306, 382/307, 382/308
• US Class Current: 707/706
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer-based technique is provided for retrieving one or more items from a database in response to a query specified by a user via one or more example sets. Preferably the example sets include multiple positive and negative example sets. The method comprises the following steps. First, a scoring function is constructed from the one or more example sets. The scoring function gives higher scores to database items that are more closely related to the query than to database items that are not as closely related to the query. The scoring function is operable for use with a multidimensional indexing structure associated with the database. Then, the one or more database items that have the highest score as computed using the scoring function are retrieved via the multidimensional indexing structure.

Claims

1. A computer-based method of retrieving one or more items from at least one database in response to a query specified by a user via a plurality of positive and negative example sets, the method comprising the steps of:

constructing a scoring function from the plurality of positive and negative example sets, wherein the scoring function is operable for use with a multidimensional indexing structure capable of supporting similarity queries and associated with the at least one database, wherein the scoring function is constructed by combining respective scoring functions of the plurality of positive and negative example sets, and wherein combining respective scoring functions comprises the steps of modifying the scoring functions of the plurality of positive and negative example sets so that the scoring functions of the positive example sets assign low scores to representative samples of the negative example sets, and so that the scoring functions of the negative example sets assign low scores to representative samples of the positive example sets, and combining the modified scoring functions of the plurality of positive and negative example sets;

querying the at least one database in accordance with the scoring function, wherein higher scores are associated with database items more closely related to the query; and

retrieving, via the multidimensional indexing structure, the one or more database items that have the highest score as computed using the scoring function.

2. The method of claim 1, wherein the scoring function assigns a score to an element of a search space associated with the at least one database equal to the minimum of:

(i) the maximum of the scores assigned to the element by the scoring functions of the positive example sets; and

(ii) the minimum of one minus the scores assigned to the element by the scoring functions of the negative example sets.

3. The method of claim 1, wherein the scoring function gives higher scores to database items that are more closely related to the query than to database items that are not as closely related to the query.

4. The method of claim 1, wherein the scoring function is obtained for each of the plurality of positive and negative example sets by:

computing a characteristic example from each example set;

computing a dispersion characterization of each example set in association with the characteristic example; and

using the characteristic example, the dispersion characterization, and one or more samples from the database to compute the scoring function.

5. The method of claim 4, wherein the characteristic example is a centroid, a median, or a mode computed over at least a portion of the example set.

6. The method of claim 4, wherein the dispersion characterization associated with the example set comprises a covariance matrix, a standard deviation, central moments, order statistics of differences, or third moments capturing asymmetry.

7. The method of claim 4, wherein the step of using the characteristic example, the dispersion characterization, and one or more samples from the database to compute the scoring function further comprises computing weighted distances between the characteristic example and the one or more samples from the database using the dispersion characterization to compute weights.

8. The method of claim 7, wherein the weighted distances are Euclidean distances or Minkowsky distances.

9. The method of claim 1, wherein the scoring function is computed for each of the plurality of positive and negative example sets by converting one or more semi-metrics obtained using the each example set to one or more scores using a conversion function.

10. The method of claim 9, wherein the semi-metrics are weighted Minkowsky distances from a representative sample of examples in each of the plurality of positive and negative example sets, and further wherein weights are calculated using the examples in each example set.

11. The method of claim 10, wherein the weights are the inverse of standard deviations of the examples in each example set.

12. The method of claim 10, wherein the representative sample is a centroid of the examples in each example set.

13. The method of claim 9, wherein the conversion function is a monotonically non-increasing continuous function having a value equal to one at the origin and a value of zero at infinity.

14. The method of claim 13, wherein the conversion function is a monotonically non-increasing continuous function having a value of one between zero and a first threshold value and a value of zero after a second threshold value.

15. The method of claim 1, wherein the user specifies the number of items to retrieve from the database.

16. The method of claim 1, wherein the retrieving step further comprises the step of searching the multidimensional indexing structure to retrieve from the database the items having the highest score.

17. The method of claim 16, wherein the multidimensional indexing structure is used to execute different queries.

18. The method of claim 16, wherein the multidimensional indexing structure is based on a recursive partition of a search space associated with the database using hyperplanes parallel to coordinate axes or surfaces other than hyperplanes parallel to coordinate axes.

19. The method of claim 16, wherein searching the multidimensional indexing structure comprises the steps of:

using scoring functions of the plurality of positive and negative example sets to search a tree to identify candidate nodes; and

using the scoring functions of the plurality of positive and negative example sets to score items stored at leaves of the multidimensional indexing structure.

20. The method of claim 19, wherein identifying candidate nodes comprises the steps of:

computing for each scoring function of the positive example sets, the maximum possible score of an item stored at the node or at one of the descendants of the node;

computing the maximum of the maximum scores;

computing for each scoring function of the negative example sets, the minimum possible score of an item stored at the node or at one of the descendants of the node;

computing the minimum of one minus the minimum scores;

computing the minimum of;

(i) the maximum of the maximum scores; and

(ii) the minimum of one minus the minimum scores;

comparing the computed minimum to the minimum of the scores in a current result set;

declaring that a node is a candidate if the minimum is not smaller than the minimum of the scores in the current result set; and

declaring that the node is not a candidate otherwise.

21. The method of claim 19, wherein the search is performed by using the scoring functions of the positive example sets one at a time in conjunction with the scoring functions of the negative example sets.

22. Apparatus for retrieving one or more items from at least one database in response to a query specified by a user via a plurality of positive and negative example sets, the apparatus comprising:

at least one processor operative to;

(i) construct a scoring function from the plurality of positive and negative example sets, wherein the scoring function is operable for use with a multidimensional indexing structure capable of supporting similarity queries and associated with the at least one database, wherein the scoring function is constructed by combining respective scoring functions of the plurality of positive and negative example sets, and wherein combining respective scoring functions comprises the steps of modifying the scoring functions of the plurality of positive and negative example sets so that the scoring functions of the positive example sets assign low scores to representative samples of the negative example sets, and so that the scoring functions of the negative example sets assign low scores to representative samples of the positive example sets, and combining the modified scoring functions of the plurality of positive and negative example sets;

(ii) query the at least one database in accordance with the scoring function, wherein higher scores are associated with database items more closely related to the query; and

(iii) retrieve, via the multidimensional indexing structure, the one or more database items that have the highest score as computed using the scoring function; and

memory, coupled to the at least one processor, for storing at least a portion of results of one or more of the constructing and retrieving operations.

23. The apparatus of claim 22, wherein the scoring function assigns a score to an element of a search space associated with the at least one database equal to the minimum of:

(i) the maximum of the scores assigned to the element by the scoring functions of the positive example sets; and

(ii) the minimum of one minus the scores assigned to the element by the scoring functions of the negative example sets.

24. The apparatus of claim 22, wherein the scoring function gives higher scores to database items that are more closely related to the query than to database items that are not as closely related to the query.

25. The apparatus of claim 22, wherein a scoring function is obtained for the each of the plurality of positive and negative example sets by:

(i) computing a characteristic example from each example set;

(ii) computing a dispersion characterization of each example set in association with the characteristic example; and

(iii) using the characteristic example, the dispersion characterization, and one or more samples from the database to compute the scoring function.

26. The apparatus of claim 25, wherein the characteristic example is a centroid, a median, or a mode computed over at least a portion of the example set.

27. The apparatus of claim 25, wherein the dispersion characterization associated with the example set comprises a covariance matrix, a standard deviation, central moments, order statistics of differences, or third moments capturing asymmetry.

28. The apparatus of claim 25, wherein the operation of using the characteristic example, the dispersion characterization, and one or more samples from the database to compute the scoring function further comprises computing weighted distances between the characteristic example and the one or more samples from the database using the dispersion characterization to compute weights.

29. The apparatus of claim 28, wherein the weighted distances are Euclidean distances or Minkowsky distances.

30. The apparatus of claim 22, wherein a scoring function is computed for each of the plurality of positive and negative example sets by converting one or more semi-metrics obtained using the each example set to one or more scores using a conversion function.

31. The apparatus of claim 30, whereinthe semi-metrics are weighted Minkowsky distances from a representative sample of examples in each of the plurality of positive and negative example sets, and further wherein weights are calculated using the examples in each example set.

32. The apparatus of claim 31, wherein the weights are the inverse of standard deviations of the examples in each example set.

33. The apparatus of claim 31, wherein the representative sample is a centroid of the examples in each example set.

34. The apparatus of claim 30, wherein the conversion function is a monotonically non-increasing continuous function having a value equal to one at the origin and a value of zero at infinity.

35. The apparatus of claim 34, wherein the conversion function is a monotonically non-increasing continuous function having a value of one between zero and a first threshold value and a value of zero after a second threshold value.

36. The apparatus of claim 22, wherein the user specifies the number of items to retrieve from the database.

37. The apparatus of claim 22, wherein the retrieving step further comprises the step of searching the multidimensional indexing structure to retrieve from the database the items having the highest score.

38. The apparatus of claim 37, wherein the multidimensional indexing structure is used to execute different queries.

39. The apparatus of claim 37, wherein the multidimensional indexing structure is based on a recursive partition of a search space associated with the database using hyperplanes parallel to coordinate axes or surfaces other than hyperplanes parallel to coordinate axes.

40. The apparatus of claim 37, wherein searching the multidimensional indexing structure comprises:

(i) using scoring functions of the plurality of positive and negative example sets to search a tree to identify candidate nodes; and

(ii) using the scoring functions of the plurality of positive and negative example sets to score items stored at leaves of the multidimensional indexing structure.

41. The apparatus of claim 40, wherein identifying candidate nodes comprises:

(i) computing for each scoring function of the positive example sets, the maximum possible score of an item stored at the node or at one of the descendants of the node;

(ii) computing the maximum of the maximum scores;

(iii) computing for each scoring function of the negative example sets, the minimum possible score of an item stored at the node or at one of the descendants of the node;

(iv) computing the minimum of one minus the minimum scores;

(v) computing the minimum of;

(a) the maximum of the maximum scores; and

(b) the minimum of one minus the minimum scores;

(vi) comparing the computed minimum to the minimum of the scores in a current result set;

(vii) declaring that a node is a candidate if the minimum is not smaller than the minimum of the scores in the current result set; and

(viii) declaring that the node is not a candidate otherwise.

42. The apparatus of claim 40, wherein the search is performed by using the scoring functions of the positive example sets one at a time in conjunction with the scoring functions of the negative example sets.

43. A method for making a computer implemented process to enable retrieval of one or more items from at least one database in response to a query specified by a user via a plurality of positive and negative example sets, the method comprising the steps of:

instantiating first computer instructions onto a computer readable medium, the first computer instructions configured to construct a scoring function from the plurality of positive and negative example sets, wherein the scoring function is operable for use with a multidimensional indexing structure capable of supporting similarity queries and associated with the at least one database, wherein the scoring function is constructed by combining respective scoring functions of the plurality of positive and negative example sets, and wherein combining respective scoring functions comprises the steps of modifying the scoring functions of the plurality of positive and negative example sets so that the scoring functions of the positive example sets assign low scores to representative samples of the negative example sets, and so that the scoring functions of the negative example sets assign low scores to representative samples of the positive example sets, and combining the modified scoring functions of the plurality of positive and negative example sets;

instantiating second computer instructions onto a computer readable medium, the second computer instructions configured to query the at least one database in accordance with the scoring function, wherein higher scores are associated with database items more closely related to the query; and

instantiating third computer instructions onto a computer readable medium, the third computer instructions configured to retrieve, via the multidimensional indexing structure, the one or more database items that have the highest score as computed using the scoring function.