METHOD AND APPARATUS FOR DETERMINING RELEVANT SEARCH RESULTS USING A MATRIX FRAMEWORK

• US 20110016118A1
• Filed: 07/20/2009
• Published: 01/20/2011
• Est. Priority Date: 07/20/2009
• Status: Active Grant

• Current Assignee: RELX Inc. (RELX PLC)
• Original Assignee: LexisNexis Group Inc. (RELX PLC)
• Inventors: Miller, David James, Loritz, Donald, EDALA, Narasimha
• Granted Patent: US 8,478,749 B2
• Time in Patent Office: Days
• US Class Current: 707/730
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method and apparatus are provided for ranking documents according to relevancy scoring. In one implementation, a computer-implemented method is provided for receiving search results identifying a plurality of documents resulting from a search, the plurality of documents containing one or more words. The method generates a first matrix containing a term column and a document column, wherein at least one row of the first matrix correlates one of the plurality of documents with one of the terms. The method selects a sort preference, and sorts the two-column matrix according to the sort preference. The method further generates a second matrix containing values representing a measure of overlap between the plurality of documents and the terms. The method further calculates cumulative confidence scores according to the values of the second matrix and ranks the search results according to the cumulative confidence scores.

Claims

1. A computer-implemented method of determining relevant search items, the method comprising the steps performed by a computer of:

receiving search results identifying a plurality of documents resulting from a search, the plurality of documents containing one or more terms;

generating a first matrix containing a term column representing the one or more terms and a document column representing the documents, wherein at least one row of the first matrix correlates one of the plurality of documents with one of the terms;

selecting the document column of the first matrix or the term column of the first matrix as a sort preference;

sorting the first matrix according to the sort preference;

generating a second matrix containing values representing a measure of overlap between the plurality of documents and the terms, based on the sorted first matrix; and

calculating cumulative confidence scores according to the values of the second matrix and ranking the search results according to the cumulative confidence scores.

2. The method of claim 1, wherein the terms are phrases including a plurality of words.

3. The method of claim 1, wherein the first matrix is sorted according to the term column, and then sorted according to the document column, such that documents sharing a common term are in immediate succession of one another in the sorted first matrix.

4. The method of claim 3, further comprising determining a position in the second matrix, based on the documents sharing a common term in the sorted first matrix, and incrementing a value of the second matrix at the determined position.

5. The method of claim 1, wherein the calculated cumulative confidence scores are determined by normalizing the second matrix with a third matrix, the third matrix having values determined by logical unions between pairs of the plurality of documents.

6. The method of claim 5, wherein the normalization of the second matrix with the third matrix calculates percentage similarities between the plurality of documents, and rows of the normalized second matrix are summed to determine the cumulative confidence scores.

7. The method of claim 1, wherein the first matrix is sorted according to the document column, and then sorted according to the term column, such that terms common to one of the plurality of documents are in immediate succession of one another in the sorted first matrix.

8. A computer-readable storage medium storing instructions which, when executed by a processor, perform a method, the method comprising:

receiving search results identifying a plurality of documents resulting from a search, the plurality of documents containing one or more terms;

generating a first matrix containing a term column representing the one or more terms and a document column representing the documents, wherein at least one row of the first matrix correlates one of the plurality of documents with one of the terms;

selecting the document column of the first matrix or the term column of the first matrix as a sort preference;

sorting the first matrix according to the sort preference;

generating a second matrix containing values representing a measure of overlap between the plurality of documents and the terms, based on the sorted first matrix; and

calculating cumulative confidence scores according to the values of the second matrix and ranking the search results according to the cumulative confidence scores.

9. The computer-readable storage medium of claim 8, wherein the terms are phrases including a plurality of words.

10. The computer-readable storage medium of claim 8, wherein the first matrix is sorted according to the term column, and then sorted according to the document column, such that documents sharing a common term are in immediate succession of one another in the sorted first matrix.

11. The computer-readable storage medium of claim 10, further comprising determining a position in the second matrix, based on the documents sharing a common term in the sorted first matrix, and incrementing a value of the second matrix at the determined position.

12. The computer-readable storage medium of claim 8, wherein the calculated cumulative confidence scores are determined by normalizing the second matrix with a third matrix, the third matrix having values determined by logical unions between pairs of the plurality of documents.

13. The computer-readable storage medium of claim 12, wherein the normalization of the second matrix with the third matrix calculates percentage similarities between the plurality of documents, and rows of the normalized second matrix are summed to determine the cumulative confidence scores.

14. The computer-readable storage medium of claim 8, wherein the first matrix is sorted according to the document column, and then sorted according to the term column, such that terms common to one of the plurality of documents are in immediate succession of one another in the sorted first matrix.

15. An apparatus comprising:

a memory device storing instructions for determining relevant search results; and

a processor executing the instructions to perform the steps of;

receiving search results identifying a plurality of documents resulting from a search, the plurality of documents containing one or more terms;

generating a first matrix containing a term column representing the one or more terms and a document column representing the documents, wherein at least one row of the first matrix correlates one of the plurality of documents with one of the terms;

selecting the document column of the first matrix or the term column of the first matrix as a sort preference;

sorting the first matrix according to the sort preference;

generating a second matrix containing values representing a measure of overlap between the plurality of documents and the terms, based on the sorted first matrix; and

calculating cumulative confidence scores according to the values of the second matrix and ranking the search results according to the cumulative confidence scores.

16. The apparatus of claim 15, wherein the terms are phrases including a plurality of words.

17. The apparatus of claim 15, wherein the first matrix is sorted according to the term column, and then sorted according to the document column, such that documents sharing a common term are in immediate succession of one another in the sorted first matrix.

18. The apparatus of claim 17, further comprising determining a position in the second matrix, based on the documents sharing a common term in the sorted first matrix, and incrementing a value of the second matrix at the determined position.

19. The apparatus of claim 15, wherein the calculated cumulative confidence scores are determined by normalizing the second matrix with a third matrix, the third matrix having values determined by logical unions between pairs of the plurality of documents.

20. The computer-readable storage medium of claim 19, wherein the normalization of the second matrix with the third matrix calculates percentage similarities between the plurality of documents, and rows of the normalized second matrix are summed to determine the cumulative confidence scores.

21. The computer-readable storage medium of claim 15, wherein the first matrix is sorted according to the document column, and then sorted according to the term column, such that terms common to one of the plurality of documents are in immediate succession of one another in the sorted first matrix.

22. A computer-implemented method for providing relevant documents to a client computer, the method comprising:

sending, to a remote computer system via a network, a search query containing query terms;

obtaining, at the remote computer system, documents resulting from performing the search query on a document database;

generating a first matrix representing a measure of overlap of terms among the documents;

generating a second matrix representing a logical union of all terms among the documents;

generating a third matrix, the coefficients of the third matrix being calculated based on the coefficients of the first matrix and the coefficients of the second matrix;

calculating cumulative confidence scores by summing rows of the third matrix; and

ranking the search results in an order according to the cumulative confidence scores.

23. The method of claim 22, wherein the coefficients of the third matrix γ

_m,n are calculated, based on the first matrix α

_m,n and second matrix β

_m,n according to;

γ

_m,n=α

_m,n/(β

_m,n−

α

_m,n).