Information retrieval method with efficient similarity search capability

• US 7,734,566 B2
• Filed: 11/01/2004
• Issued: 06/08/2010
• Est. Priority Date: 11/01/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schmitt, Sascha H., Niekamp, Tobias, Caracas, Alexandru M.
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Choi; Michele C
• Application Number:
  US10/980,117
• Publication Number:
  US 20060106762A1
• Time in Patent Office: 2,045 Days
• Field of Search: 707/6, 707/101, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Embodiments of the present invention include methods for retrieving information from an information base. In one embodiment, the present invention includes specifying a first query including one or more specified attribute values corresponding to one or more attributes, performing a count-only query on a structured information base for information elements having one or more attribute values within a first range, the first range including the specified attribute values, and performing a retrieval query for information elements having one or more attribute values within a second range, wherein the second range includes the first range.

Claims

1. A computer-implemented method of retrieving information comprising:

receiving a first query from a user, the first query including a plurality of specified attribute values corresponding to a plurality of attributes, wherein the first query includes at least a first attribute having a corresponding first attribute value and a second attribute having a corresponding second attribute value;

in response to the first query, automatically performing, on the computer, steps as follows;

automatically generating a first range from the plurality of specified attribute values, the first range comprising a first plurality of attribute values for the first attribute, the first plurality of attribute values defining a first attribute range that includes the first attribute value; and

a second plurality of attribute values for the second attribute, the second plurality of attribute values defining a second attribute range that includes the second attribute value;

performing a count-only query on a structured information base for information elements having attribute values within the first range, wherein the count-only query returns a first value representing a number of information elements in the structured information base having (i) said first attribute, (ii) an attribute value of said first attribute within the first attribute range, (iii) said second attribute, and (iv) an attribute value of said second attribute within the second attribute range; and

if the first value is less than a specified minimum number of desired results, increasing the first range and repeating said count-only query, and if the first value is greater than or equal to the specified minimum number of desired results,

automatically generating a second range from the plurality of specified attribute values, the second range comprising a third plurality of attribute values for the first attribute, the third plurality of attribute values defining a third attribute range that is greater than or equal to the first attribute range, and a fourth plurality of attribute values for the second attribute, the fourth plurality of attribute values defining a fourth attribute range that is greater than or equal to the second attribute range; and

performing a retrieval query for information elements having attribute values within the second range, wherein the retrieval query returns information elements in the structured information base having (i) said first attribute, (ii) an attribute value of said first attribute within the third plurality of attribute values, (iii) said second attribute, and (iv) an attribute value of said second attribute within the fourth plurality of attribute values; and

in response to the first query, automatically returning said information elements having attribute values within the second range to the user.

2. The method of claim 1 wherein the first value is an integer number equal to the number of information elements having a global similarity to the first and second attribute values greater than a threshold value.

3. The method of claim 2 wherein the threshold value is equal to a sum of weighted local similarity values.

4. The method of claim 2 wherein the first range is generated using one or more local similarities.

5. The method of claim 4 wherein the first range is generated using inverse similarity functions.

6. The method of claim 1 wherein the second range is generated using one or more minimal local similarities.

7. The method of claim 6 wherein the second range is generated using inverse similarity functions.

8. The method of claim 2 wherein an initial threshold value is based on a probability of obtaining a minimum number (K) of information elements.

9. The method of claim 8 wherein the initial threshold value is changed if the count-only query returns a value that is less than the minimum number (K).

10. The method of claim 1 wherein the first query comprises the specified minimum number of desired results.

11. The method of claim 1 wherein the first query includes one or more weights corresponding to the one or more attributes.

12. The method of claim 1 further comprising defining a similarity model.

13. The method of claim 12 wherein the similarity model comprises one or more local similarity functions or inverse similarity functions corresponding to the one or more attributes in the first query.

14. The method of claim 13 wherein the one or more local or inverse similarity functions include a numeric function, a matrix, or a taxonomy.

15. The method of claim 1 wherein the information elements are electronic documents, objects, rows of a database table, or an XML file.

16. The method of claim 1 wherein the first query includes M attribute values corresponding to M attributes and the first and second ranges are M-dimensional.

17. A computer-implemented method of retrieving information comprising:

receiving, from a user, a first query including a plurality of specified attribute values corresponding to a plurality of attributes;

upon execution of the first query, automatically performing, on a computer, the following steps;

generating a threshold value;

generating a local similarity value for each of the plurality of attributes based on the threshold value;

generating a first range based on each local similarity value, the first range including the specified attribute values;

performing a count-only query on a structured information base for information elements having one or more attribute values within the first range, wherein the count-only query returns a first value representing a number of information elements having attribute values within the first range;

if the first value is less than a specified minimum number of desired results, increasing the first range and repeating said count-only query, and if the first value is greater than or equal to the specified minimum number of desired results, then performing a retrieval query for information elements having one or more attribute values within a second range, wherein the second range is greater than or equal to the first range; and

wherein performing the retrieval query comprises;

automatically generating the second range from the plurality of specified attribute values, the second range including a first plurality of attribute values for a first attribute, the first plurality of attribute values defining a first attribute range, and a second plurality of attribute values for a second attribute, the second plurality of attribute values defining a second attribute range, wherein the retrieval query returns information elements in the structured information base having (i) said first attribute, (ii) an attribute value of said first attribute within the first plurality of attribute values, (iii) said second attribute, and (iv) an attribute value of said second attribute within the second plurality of attribute values; and

returning the information elements having one or more attribute values within the second range to the user.

18. The method of claim 17 wherein the threshold value is based on a global similarity threshold.

19. The method of claim 18 wherein the global similarity threshold is equal to a sum of weighted local similarity values.

20. The method of claim 17 wherein the first range is generated using inverse similarity functions.

21. The method of claim 17 wherein the second range is generated using the threshold and a plurality of minimal local similarities.

22. The method of claim 21 wherein generating the second range includes calculating the minimal local similarities based on the threshold and calculating a plurality of attribute values to define endpoints of the second range using the minimal local similarities and inverse similarity functions.

23. The method of claim 17 wherein the first query comprises the specified minimum number of desired results, and wherein the threshold is changed if the count-only query returns fewer than said minimum number of information elements.

24. The method of claim 17 wherein the first query includes one or more weights corresponding to the one or more attributes.

25. The method of claim 17 wherein the first query includes M attribute values corresponding to M attributes and the first and second ranges are M-dimensional.