Techniques for finding related hyperlinked documents using link-based analysis

• US 6,754,873 B1
• Filed: 04/06/2000
• Issued: 06/22/2004
• Est. Priority Date: 09/20/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R., Law, Kin Lun
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): Basehoar, Adam L.
• Application Number:
  US09/544,733
• Time in Patent Office: 1,538 Days
• Field of Search: 715/501.1, 715/514, 715/513, 707/4, 707/5, 707/3
• US Class Current: 715/208
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Techniques for finding related hyperlinked documents using link-based analysis are provided. Backlink and forwardlink sets can be utilized to find web pages that are related to a selected web page. The scores for links from web pages that are from the same host and links from web pages with numerous links can be reduced to achieve a better list of related web pages. The list of related web pages can be utilized as a feature to a word-based search engine or an addition to a web browser.

Claims

1. A computer implemented method of generating lists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have a forward link to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set;

assigning values to the forward links in the hyperlinked documents in the first set, the value being reduced for a forward link if there are multiple hyperlinked documents from the same host as the hyperlinked document that includes the forward link;

wherein the value is further reduced by dividing the value based on a number of forward links in the hyperlinked documents that includes the forward link plus a predetermined amount;

generating a score for each hyperlinked document in the second set based on the values of the forward links pointing to the hyperlinked document, and

generating a first list of related hyperlinked documents from the second set based on the scores of the hyperlinked documents;

wherein the selected hyperlinked document is displayed in result of a search and a user request to display the first list for the selected hyperlinked document.

2. The method of claim 1, wherein the values are reduced when there are multiple hyperlinked documents from the same host by dividing the value by the number of hyperlinked documents from the same host.

3. The method of claim 1, wherein generating a list of related hyperlinked documents includes selecting hyperlinked documents in the second set that have scores above a threshold.

4. The method of claim 1, wherein generating a list of related hyperlinked documents includes selecting a predetermined number of hyperlinked documents in the second set with highest scores.

5. The method of claim 1, wherein each hyperlinked document is given a forward link to itself.

6. The method of claim 1, further comprising displaying the first list.

7. A computer implemented method of generating lists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have forward links to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set;

assigning values to the forward links in the hyperlinked documents in the first set, the value being reduced for a forward link if there are multiple hyperlinked documents from the same host as the hyperlinked document that includes the forward link;

generating a score for each hyperlinked document in the second set according to the values of the forward links pointing to the hyperlinked document; and

generating a first list of related hyperlinked documents from the second set according to the scores of the hyperlinked documents;

wherein the value of a forward link is reduced based on the number of forward links in the hyperlinked document that includes the forward link; and

wherein the value is reduced by dividing the value by a number based on the number of forward links plus a predetermined amount.

8. A computer implemented method of generating lists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have forward links to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set;

assigning values to the forward links in the hyperlinked documents in the first set, the value being reduced for a forward link if there are multiple hyperlinked documents from the same host as the hyperlinked document that includes the forward link, and the value being further reduced by dividing the value based on a number of forward links plus a predetermined amount;

generating a score for each hyperlinked document in the second set according to the values of the forward links pointing to the hyperlinked document;

generating a first list of related hyperlinked documents from the second set based on the scores of the hyperlinked documents;

generating a second list of related hyperlinked documents for each of the hyperlinked documents in the first list; and

removing a hyperlinked document from the first list if the selected hyperlinked document is not in the second list of a hyperlinked document in the first set.

9. The method of claim 8, further comprising generating a third list of related hyperlinked documents that includes each of the hyperlinked documents that is removed from the first list.

10. The method of claim 9, further comprising removing a hyperlinked document from the third list if the selected hyperlinked document is in a third set of hyperlinked documents, the third set being hyperlinked documents that are a most popularly occurring set of hyperlinked documents that are determined to be related to other hyperlinked documents.

11. The method of claim 10, further comprising generating the third set by generating a list of related hyperlinked documents for each hyperlinked document and selecting a predetermined number of hyperlinked documents that appear in the lists of related hyperlinked documents most often.

12. A computer implemented method of generating lists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have forward links to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set;

assigning values to the forward links in the hyperlinked documents in the first set, the value being reduced for a forward link if there are multiple hyperlinked documents from the same host as the hyperlinked document that includes the forward link, and the value being further reduced by dividing the value based on a number of forward links plus a predetermined amount;

generating a score for each hyperlinked document in the second set based on the values of the forward links pointing to the hyperlinked document; and

generating a first list of related hyperlinked documents from the second set based on the scores of the hyperlinked documents;

wherein the selected hyperlinked document is displayed in a web browser and a user requests to display the first list for the selected hyperlinked document.

13. A computer implemented method of generating lists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have forward links to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set;

assigning values to forward links in the hyperlinked documents in the first set, the value being reduced by dividing the value based on a number of forward links in the hyperlinked document that includes the forward link plus a predetermined amount;

generating a score for each hyperlinked document in the second set according to the values of the forward links pointing to the hyperlinked document; and

generating a first list of related hyperlinked documents from the second set based on the scores of the hyperlinked documents;

wherein the selected hyperlinked document is displayed in result of a search and a user request to display the first list for the selected hyperlinked document.

14. The method of claim 13, wherein the value is reduced for a forward link if there are multiple hyperlinked documents from the same host as the hyperlinked document that includes the forward link.

15. The method of claim 13, wherein generating a list of related hyperlinked documents includes selecting hyperlinked documents in the second set that have scores above a threshold.

16. The method of claim 13, wherein generating a list of related hyperlinked documents includes selecting a predetermined number of hyperlinked documents in the second set with highest scores.

17. The method of claim 13, wherein each hyperlinked document is given a forward link to itself.

18. A computer implemented method of generating fists of related hyperlinked documents, comprising:

providing a first set of hyperlinked documents that have forward links to a selected hyperlinked document and a second set of hyperlinked documents that are pointed to by the forward links in the hyperlinked documents of the first set,

assigning values to forward links in the hyperlinked documents in the first set, the value being reduced based on the number of forward links in the hyperlinked document that includes the forward link;

generating a score for each hyperlinked document in the second set according to the values of the forward links pointing to the hyperlinked document; and

generating a first list of related hyperlinked documents from the second set according to the scores of the hyperlinked documents;

wherein the value is reduced by dividing the value by a number based on a number of forward links plus a predetermined amount.

19. The method of claim 18, wherein the value is further reduced by dividing the value by the number of hyperlinked documents from the same host.