Techniques for finding related hyperlinked documents using link-based analysis

• US 7,634,716 B1
• Filed: 12/30/2003
• Issued: 12/15/2009
• Est. Priority Date: 09/20/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Law, Kin Lun, Harik, Georges R.
• Primary Examiner(s): Basehoar; Adam L
• Application Number:
  US10/747,043
• Time in Patent Office: 2,177 Days
• Field of Search: 715/501.1, 715/513, 715/205, 715/206, 715/207, 715/208, 715/234, 707 2- 5, 707/100, 707/10, 707/101, 707/102, 707/104.1, 707/1, 707/7
• US Class Current: 715/205
• 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 method of generating lists of related documents performed by a computer system, the method comprising:

providing, by a processor of the computer system, a first set of documents that link to a particular document and a second set of documents that are pointed to by forward links in the documents of the first set;

assigning, by the processor, values to the forward links in the documents in the first set;

generating, by the processor, scores for the documents in the second set based on the assigned values of the forward links;

generating, by the processor, a first list of documents that are related to the particular document by selecting a subset of documents from the second set based on the generated scores;

generating, by the processor, a second list of related documents for at least one of the documents in the first list; and

removing, by the processor, the at least one of the documents from the first list if the particular document is not in the second list.

2. The method of claim 1, where the values assigned to the forward links are reduced for a particular one of the forward links when there are multiple documents from a same host as the particular document that includes the particular one of the forward links.

3. The method of claim 2, where the values are reduced by dividing the values by the number of documents from the same host.

4. The method of claim 2, where the value of a particular one of the forward links is reduced according to the number of forward links in the particular document that includes the particular one of the forward links.

5. The method of claim 4, where the values are further reduced by dividing the values by the number of forward links.

6. The method of claim 4, where the values are further reduced by dividing each of the values by the number of forward links plus a particular number.

7. The method of claim 1, where generating the first list of documents includes selecting documents in the second set that have scores above a threshold.

8. The method of claim 1, where generating the first list of documents includes selecting a predetermined number of documents in the second set with highest scores.

9. The method of claim 1, where each of the documents includes a forward link to itself.

10. The method of claim 1, further comprising:

generating a third list of documents that includes each of the documents that is removed from the first list.

11. The method of claim 10, further comprising:

presenting documents related to the particular document to a user as documents included in the first list and the third list of documents, in which the documents in the first list are presented first to the user followed by the documents in the third list.

12. The method of claim 11, where the documents in the first list are symmetrically related to the particular document and the documents in the third list are unsymmetrically related to the particular document.

13. The method of claim 1, further comprising presenting the first list for display.

14. The method of claim 1, where the particular document is displayed in a web browser when a user requests to display the first list for the particular document.

15. The method of claim 1, where the particular document is displayed in results of a search when a user requests to display the first list for the particular document.

16. A computer program product, embodied within a computer readable memory device, for generating lists of related documents, comprising:

computer code that receives a first set of documents that link to a particular document and a second set of documents that are pointed to by forward links in the documents of the first set;

computer code that assigns values to the forward links in the documents in the first set;

computer code that generates scores for the documents in the second set based on the assigned values of the forward links;

computer code that generates a first list of documents that are related to the particular document by selecting a subset of documents from the second set based on the generated scores;

computer code that generates a second list of related documents for at least one of the documents in the first list; and

computer code that removes the at least one of the documents from the first list if the particular document is not in the second list.

17. The computer program product of claim 16, where the assigned values are reduced for a forward link if there are multiple documents from a same host as the document that includes the forward link.

18. The computer program product of claim 16, where the computer readable memory device is a CD-ROM, floppy disk, tape, flash memory, system memory, or a hard drive.

19. A method of generating lists of related documents performed by a computer system, the method comprising:

providing, by a processor of the computer system, a first set of documents that have forward links to a particular document and a second set of documents that are pointed to by the forward links in the documents of the first set;

assigning, by the processor, values to forward links in the documents in the first set;

generating, by the processor, scores for the documents in the second set based on the assigned values of the forward links that point to the documents in the second set;

generating, by the processor, a first list of documents that are related to the particular document by selecting documents from the second set based on the generated scores;

generating, by the processor, second lists of related documents for the documents in the first list;

categorizing, by the processor, a document from the first list as being symmetrically related to the particular document when the particular document is in the second list corresponding to the document;

categorizing, by the processor, a document from the first list as being unsymmetrically related to the particular document when the particular document is not in the second list corresponding to the document;

presenting, by a network device or by a display device of the computer system, the first list of documents in a presentation order based on the categorization.

20. The method of claim 19, where assigning values to forward links in the documents in the first set includes reducing the assigned values based on the number of forward links in the document that includes the forward links.

21. The method of claim 20, where the values are reduced by dividing the values by the number of forward links.

22. The method of claim 20, where the values are reduced by dividing the values by the number of forward links plus a particular number.

23. The method of claim 20, where the values are reduced for a forward link if there are multiple documents in the first set from the same host as the document that includes the forward link.

24. The method of claim 19, where each document includes a forward link to itself.

25. The method of claim 19, further comprising presenting the first list.

26. The method of claim 19, where the particular document is displayed in a web browser when a user requests to display the first list for the particular document.

27. The method of claim 19, where the particular document is displayed in results of a search when a user requests to display the first list for the particular document.

28. A method of generating a list of documents related to a particular document performed by a computer system, the method comprising:

receiving, by a processor of the computer system, a first set of documents that have forward links to the particular document;

receiving, by the processor, a second set of documents that are pointed to by forward links in the documents of the first set;

assigning, by the processor, values to the forward links of the documents in the first set;

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

selecting, by the processor, documents from the second set based on the scores of the documents in the second set to generate the list of documents related to the particular document;

generating, by the processor, second lists of related documents for the documents in the list of documents related to the particular document; and

removing, by the processor, a particular document from the list of documents related to the particular document if the particular document is not in the second list corresponding to the particular document.

29. The method of claim 28, further comprising:

generating a third list of documents that includes each of the documents that is removed from the list of documents related to the particular document.

30. The method of claim 29, further comprising:

presenting documents related to the particular document to a user as documents included in the first list and the third list, in which documents in the first list are displayed first to the user followed by documents in the third list.

31. The method of claim 29, where the documents in the first list are symmetrically related to the particular document and the documents in the third list are unsymmetrically related to the particular document.