Scoring documents in a linked database

• US 8,521,730 B1
• Filed: 05/30/2012
• Issued: 08/27/2013
• Est. Priority Date: 01/10/1997
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Page, Lawrence
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US13/483,859
• Time in Patent Office: 454 Days
• Field of Search: None
• US Class Current: 707/726
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database. The rank assigned to a document is calculated from the ranks of documents citing it. In addition, the rank of a document is calculated from a constant representing the probability that a browser through the database will randomly jump to the document. The method is particularly useful in enhancing the performance of search engine results for hypermedia databases, such as the world wide web, whose documents have a large variation in quality.

Claims

1. A method performed by a computer, the method comprising:

selecting, by the computer, a first document from a plurality of documents stored in a database;

generating, by the computer, a rank for the first document using;

2. The method of claim 1, where α

refers to a value in a finite range of values between zero and one.

3. The method of claim 1, where a refers to a probability that a user, when accessing a particular document of the one or more second documents, will randomly access another particular document, of the plurality of documents, rather than following the link to the first document,

the particular document being different from the other particular document.

4. The method of claim 1, further comprising:

performing a plurality of iterations of selecting the first document, generating the rank for the first document, and storing the rank for the first document.

5. The method of claim 1, further comprising:

repeating selecting a document, generating a rank, and storing the rank for each document of the plurality of documents stored in the database.

6. The method of claim 1, where the first document is from a first domain, and

where the one or more second documents include only documents from one or more second domains,

the one or more second domains being different from the first domain.

7. The method of claim 1, where the first document is hosted on a first web server,

where a particular document, of the one or more second documents, is hosted on the first web server and includes a first link to the first document,

where another particular document, of the one or more second documents, is hosted on a second web server and includes a second link to the first document, the second web server being different from the first web server,

where the method further comprises:

assigning a first weight to the first link based on the first document and the particular document being hosted on the first web server; and

assigning a second weight to the second link based on the first document being hosted on the first web server and the other particular document being hosted on the second web server,

the second weight being greater than the first weight;

where generating the rank for the first document includes;

generating the rank for the first document based on the first weight and the second weight.

8. The method of claim 1, where the first document is from a first domain,

where a particular document, of the one or more second documents, is from the first domain and includes a first link to the first document,

where another particular document, of the one or more second documents, is from a second domain and includes a second link to the first document, the second domain being different from the first domain,

where the method further comprises:

assigning a first weight to the first link based on the first document and the particular document being from the first domain; and

assigning a second weight to the second link based on the first document being from the first domain and the other particular document being from the second domain,

the second weight being greater than the first weight;

where generating the rank for the first document includes;

generating the rank for the first document based on the first weight and the second weight.

9. The method of claim 1, where the first document is associated with a first institution or author,

where a particular document, of the one or more second documents, is associated with the first institution or author and includes a first link to the first document,

where another particular document, of the one or more second documents, is associated with a second institution or author and includes a second link to the first document, the second institution or author being different from the first institution or author,

where the method further comprises:

assigning a first weight to the first link based on the first document and the particular document being associated with the first institution or author; and

assigning a second weight to the second link based on the first document being associated with the first institution or author and the other particular document being associated with the second institution or author,

the second weight being greater than the first weight;

where generating the rank for the first document includes;

generating the rank for the first document based on the first weight and the second weight.

10. The method of claim 1, where a particular document, of the one or more second documents, includes a first link to the first document and a second link to a third document,

the third document being different from the first document,

the first link being associated with a first measure of importance within the particular document,

the second link being associated with a second measure of importance within the first particular document,

the first measure of importance being greater than the second measure of importance,

where the method further comprises:

assigning a first weight to the first link based on the first measure of importance; and

assigning a second weight to the second link based on the second measure of importance,

the first weight being greater than the second weight;

where generating the rank for the first document includes;

generating the rank for the first document based on the first weight.

11. The method of claim 1, where a particular document, of the one or more second documents, includes a first link to the first document,

where another particular document, of the one or more second documents, includes a second link to the first document,

the particular document being associated with a first date on which the particular document was last modified,

the other particular document being associated with a second date on which the other particular document was last modified,

the first date being more recent than the second date,

where the method further comprises:

assigning a first weight to the first link based on the first date; and

assigning a second weight to the second link based on the second date,

the first weight being greater than the second weight;

where generating the rank for the first document includes;

generating the rank for the first document based on the first weight and the second weight.

12. The method of claim 1, further comprising:

identifying that the first document is associated with a home page or a bookmark of a user; and

setting a value for α

based on identifying that the first document is associated with a home page or a bookmark of the user.

13. The method of claim 1, further comprising:

obtaining real usage data relating to accesses of the plurality of documents; and

setting a value for a using the real usage data.

14. The method of claim 1, further comprising:

receiving a search query;

locating a set of documents, from the plurality of documents, based on the search query, the set of documents including the first document; and

sorting documents, in the set of documents, into a ranked list,

the first document being placed, within the ranked list, based on the rank for the first document.

15. The method of claim 14, further comprising:

determining categories associated with the documents in the set of documents; and

arranging the documents, in the ranked list, based on the determined categories associated with the documents,

a third document and a fourth document, of the documents, being associated with a same category of the determined categories,

the third document and the fourth document being grouped together within the ranked list based on the third document and the fourth document being associated with the same category.

16. The method of claim 14, further comprising:

determining sites associated with the documents in the set of documents; and

arranging the documents, in the ranked list, based on the determined sites associated with the documents,

a third document and a fourth document, of the documents, being associated with a same site of the determined sites,

the third document and the fourth document being grouped together within the ranked list based on the third document and the fourth document being associated with the same site.

17. The method of claim 1, further comprising:

receiving a search query;

locating a set of documents, from the plurality of documents, based on the search query,

the set of documents including the first document;

determining relevance ranks for documents, in the set of documents, based on a match of the search query to contents of the documents;

determining a total rank for the first document based on the rank and the relevance rank for the first document; and

sorting the documents, in the set of documents, into a ranked list,

the first document being placed, within the ranked list, based on the total rank for the first document.