Efficient Retrieval Algorithm by Query Term Discrimination

• US 20080215574A1
• Filed: 02/27/2008
• Published: 09/04/2008
• Est. Priority Date: 03/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Zheng, Zhang, Benyu, Wang, Jian, Ji, Lei, Zeng, HuaJun, Lin, Chenxi
• Granted Patent: US 7,925,644 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

An exemplary method for use in information retrieval includes, for each of a plurality of terms, selecting a predetermined number of top scoring documents for the term to form a corresponding document set for the term; receiving a plurality of terms, optionally as a query; ranking the plurality of terms for importance based at least in part on the document sets for the plurality of terms where the ranking comprises using an inverse document frequency algorithm; selecting a number of ranked terms based on importance where each selected, ranked term comprises its corresponding document set wherein each document in a respective document set comprises a document identification number; forming a union set based on the document sets associated with the selected number of ranked terms; and, for a document identification number in the union set, scanning a document set corresponding to an unselected term for a matching document identification number. Various other exemplary systems, methods, devices, etc. are also disclosed.

Claims

1. A method for use in information retrieval, the method comprising:

for each of a plurality of terms, selecting a predetermined number of top scoring documents for the term to form a corresponding document set for the term;

receiving a plurality of terms, optionally as a query;

ranking the plurality of terms for importance based at least in part on the document sets for the plurality of terms wherein the ranking comprises using an inverse document frequency algorithm;

selecting a number of ranked terms based on importance wherein each selected, ranked term comprises its corresponding document set wherein each document in a respective document set comprises a document identification number;

forming a union set based on the document sets associated with the selected number of ranked terms; and

for a document identification number in the union set, scanning a document set corresponding to an unselected term for a matching document identification number.

2. The method of claim 1 wherein the scanning comprises use of a pointer that indicates a scanning position in a document set corresponding to an unselected term.

3. The method of claim 1 wherein the scanning comprises use of jumping.

4. The method of claim 1 wherein the scanning comprises use of jumping and binary searching.

5. The method of claim 1 wherein the number of ranked terms comprise two.

6. The method of claim 1 further comprising repeating the scanning for more than one document identification number in the union set.

7. The method of claim 1 wherein the predetermined number of documents comprises a number less than approximately 25.

8. The method of claim 1 further comprising, after the scanning, comparing a document score associated with a document identification number in the document set corresponding to the unselected term to a document score associated with the document identification number in the union set.

9. The method of claim 8 further comprising, based at least in part on the comparing, jumping a pointer for the document set corresponding to the unselected term or binary searching in the document set corresponding to the unselected term.

10. The method of claim 9 wherein jumping occurs if the document score associated with a document identification number in the document set corresponding to the unselected term is less than the document score associated with the document identification number in the union set.

11. The method of claim 9 wherein binary searching occurs if the document score associated with a document identification number in the document set corresponding to the unselected term is not less than the document score associated with the document identification number in the union set.

12. The method of claim 1 wherein the scoring comprises BM25 scoring.

13. The method of claim 1 further comprising outputting a list of documents.

14. One or more computer-readable media comprising computer-executable instructions to perform the method of claim 1.

15. An offline method for use in online information retrieval, the method comprising:

for each of a plurality of terms, selecting a predetermined number of top scoring documents for the term to form a corresponding document set for the term; and

storing the document sets for subsequent access responsive to an online query.

16. The method of claim 15 wherein the scoring comprises BM25 scoring and wherein the predetermined number of top scoring documents comprises a number less than 25.

17. One or more computer-readable media comprising computer-executable instructions to perform the method of claim 15.

18. An online information retrieval method comprising:

receiving a query that comprises a plurality of terms;

accessing documents or information about documents;

based on the accessing, ranking the plurality of terms for importance;

selecting a number of ranked terms based on importance wherein each selected, ranked term comprises a corresponding document set wherein each document in a respective document set comprises a document identification number;

forming a union set based on the document sets associated with the selected number of ranked terms; and

for a document identification number in the union set, scanning a document set corresponding to an unselected term for a matching document identification number.

19. The method of claim 18 wherein the ranking comprises using an inverse document frequency algorithm.

20. One or more computer-readable media comprising processor executable instructions to perform the method of claim 18.