Determining quality of linked documents

• US 7,783,639 B1
• Filed: 06/30/2004
• Issued: 08/24/2010
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Haahr, Paul, Singhal, Amit, Bharat, Krishna
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Reyes; Mariela D
• Application Number:
  US10/879,520
• Time in Patent Office: 2,246 Days
• Field of Search: 707/102, 707/736, 707/737, 707/748, 707/749
• US Class Current: 707/736
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A ranking component ranks documents, such as web pages or web sites, to obtain a ranking score that defines a quality judgment of the document. The ranking score of a particular document is based on the ranking score of the documents which link to it and based on affiliation among the documents.

Claims

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

identifying, by a processor of the device, a plurality of documents, where a first one of the identified documents is linked by a second one of the identified documents and the second document is one of a plurality of documents in an affiliated set of documents;

calculating, by the processor, a first value for each document in the affiliated set of documents based on a ranking score of the document and a number of outbound links from the document;

calculating, by the processor, a second value as a maximum of the first values for the documents in the affiliated set of documents;

assigning, by the processor, a ranking score to the first document based the second value, where assigning the ranking score includes;

determining whether the documents in the affiliated set of documents are weakly affiliated or strongly affiliated, and

setting the amount that the second document contributes to the ranking score of the first document as a function that acts as a summation operator over the affiliated set of documents when the affiliated set is weakly affiliated and as a maximum operator over the affiliated set of documents when the affiliated set is strongly affiliated, where the function is defined as;

(CONTRIB(D₁)^a+CONTRIB(D₂)^a+ . . . +CONTRIB(D_k)^a)^1/a,

where CONTRIB for document D_k represents an individual ranking score contribution for document k in the affiliated set, and a is defined as

$\frac{1}{\mathrm{e<br><br>}+\left(1-\mathrm{e<br><br>}\right)<br><br>\mathrm{\gamma <br><br>}},$

where e is a constant and γ

represents a continuous measure of the affiliation of the documents in the affiliated set; and

storing, by the processor, the ranking score.

2. The method of claim 1, further comprising:

sorting a group of the identified documents including the first document based on the assigned ranking score.

3. The method of claim 2, further comprising:

presenting the sorted group of the identified documents to a user.

4. The method of claim 1, wherein identifying a plurality of documents includes:

identifying the plurality of documents by matching terms in a search query to terms in a collection of documents.

5. The method of claim 1, wherein the identified documents are linked via hyperlinks.

6. The method of claim 1, further comprising:

identifying affiliation among the documents in the affiliated set of documents based on at least one of a link graph structure of the documents, traffic patterns to the documents, similarity of hostnames of the documents, or similarity of IP addresses of the documents.

7. The method of claim 1, further comprising:

identifying affiliation among the documents in the affiliated set of documents based on traffic patterns between the documents.

8. The method of claim 1, wherein assigning the ranking score includes iteratively assigning the ranking score until convergence.

9. The method of claim 8, further comprising:

normalizing the ranking score after the iterative assignment of the ranking score is complete.

10. The method of claim 1, wherein the affiliation among the documents in the affiliated set of documents is defined based on a binary model of affiliation.

11. The method of claim 1, wherein the affiliation among the documents in the affiliated set of documents is defined based on a continuous model of affiliation.

12. The method of claim 1, wherein assigning the ranking score to a particular document is based on the formula:

$\mathrm{\alpha <br><br>}+\mathrm{\beta <br><br>}<br><br>\left(\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br><br><br>\mathrm{SETCONTRIB}<br><br><br><br>\left(S_i,{\mathrm{\gamma <br><br>}}_i\right)\right),$

where α and

β

are predetermined constants, the sum is taken over m affiliated sets of documents that link to the particular document, and SETCONTRIB is the function (CONTRIB(D₁)^ai+CONTRIB(D₂)^ai+ . . . +CONTRIB(D_k)^ai)^1/ai for each of the m sets of affiliated documents.

13. The method of claim 1, wherein the function is defined as:

$\frac{\mathrm{RankingScore}<br><br><br><br>\left(D\right)}{\mathrm{MAX}<br><br>\left(1,\mathrm{OutD}<br><br>\left(D\right)-\mathrm{THRESHOLD}\right)},$

where THRESHOLD is set to a predetermined value, RankingScore(D) represents the ranking score of a document D, and OutD(D) represents a number of outbound links from document D.

14. A device comprising:

a set location component to identify documents, where a first one of the documents is linked by a second one of the documents and the second document is one of a plurality of documents in an affiliated set of documents; and

a ranking component that assigns a ranking score to the first document by;

calculating a first value for each document in the affiliated set of documents based on a ranking score of the document and a number of outbound links from the document;

calculating a second value as one of the first values for the documents in the affiliated set of documents;

assigning a ranking score to the first document based the second value, where the ranking component assigns the ranking score by;

determining whether the documents in the affiliated set of documents are weakly affiliated or strongly affiliated, and

setting the amount that the second document contributes to the ranking score of the first document as a function that acts as a summation operator over the affiliated set of documents when the affiliated set is weakly affiliated and as a maximum operator over the affiliated set of documents when the affiliated set is strongly affiliated, where the function is defined as;

(CONTRIB(D₁)^a+CONTRIB(D₂)^a+ . . . +CONTRIB(D_k)^a)^1/a,

where CONTRIB for document D_k represents an individual ranking score contribution for document k in the affiliated set, and a is defined as

$\frac{1}{\mathrm{e<br><br>}+\left(1-\mathrm{e<br><br>}\right)<br><br>\mathrm{\gamma <br><br>}},$

where e is a predetermined constant and γ

represents a continuous measure of the affiliation of the documents in the affiliated set; and

storing the ranking score.

15. The device of claim 14, wherein the documents are linked via hyperlinks.

16. The device of claim 14, wherein the set location component identifies affiliations among the documents in the affiliated set of documents based on at least one of a link graph structure of the documents, traffic patterns to the documents, similarity of hostnames of the documents, or similarity of IP addresses of the documents.

17. The device of claim 14, wherein assigning the ranking score includes iteratively assigning the ranking score.

18. The device of claim 17, wherein the ranking component additionally normalizes the ranking score after the iterative assignment of the ranking score is complete.

19. The device of claim 14, wherein affiliation among the documents in the affiliated set of documents is defined based on a binary model of affiliation.

20. The device of claim 14, wherein affiliation among the documents in the affiliated set of documents is defined based on a continuous model of affiliation.

21. The device of claim 14, further comprising:

a database containing the collection of documents.