Information retrieval method with efficient similarity search capability

• US 20060106762A1
• Filed: 11/01/2004
• Published: 05/18/2006
• 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.
• Granted Patent: US 7,734,566 B2
• Time in Patent Office: Days
• 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 method of retrieving information comprising:

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.

2. The method of claim 1 wherein the count-only query returns a value equal to the number information elements having a global similarity to the first query 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 specifies a minimum number (K) of information elements to be retrieved.

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 method of retrieving information comprising:

specifying a first query including one or more specified attribute values corresponding to one or more attributes;

generating a threshold value;

generating a local similarity value for each of the one or more 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; 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.

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 one or more minimal local similarities.

23. The method of claim 17 wherein the first query specifies a minimum number (K) of information elements to be retrieved.

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.

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