Link based clustering of hyperlinked documents

• US 7,213,198 B1
• Filed: 08/10/2000
• Issued: 05/01/2007
• Est. Priority Date: 08/12/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R.
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Queler; Adam
• Application Number:
  US09/636,052
• Time in Patent Office: 2,455 Days
• Field of Search: 715/501.1, 715/526, 715/515, 715/513, 707/104.1, 707 1- 10, 707100-103, 707200-206, 704/9, 709/218
• US Class Current: 715/234
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Techniques for grouping hyperlinked documents are provided. Links near or in the neighborhood of the hyperlinked documents are analyzed in order to group the hyperlinked documents by topic. For example, links that are search results can be grouped by identifying other hyperlinked documents that have multiple forward links to the search results. The search results can then be grouped according to the forward links of the other hyperlinked documents.

Claims

1. An automated method, comprising:

identifying a set of documents;

determining whether first and second documents in the set of documents are similar based on a number of documents that point to both the first and second documents and a number of back links associated with the first and second documents, where a result of the determination of whether the first and second documents are similar is inversely proportional to the number of back links associated with the first and second documents; and

forming a group from the first and second documents when the first and second documents are determined to be similar.

2. The method of claim 1, further comprising:

determining whether a third document in the set of documents is similar to the group based on a number of documents that point to both the third document and a document in the group; and

adding the third document to the group when the third document is determined to be similar to the group.

3. The method of claim 1, further comprising:

determining whether a second group is similar to the group based on a number of documents that point to documents in both the group and the second group; and

merging the group and the second group when the second group is determined to be similar to the group.

4. The method of claim 1, wherein determining whether first and second documents in the set of documents are similar is based on subtracting a product of the number of back links associated with the first document and the number of back links associated with the second document from the number of documents that point to both the first and second documents.

5. The method of claim 1, wherein the first document corresponds to a first group of documents and the second document corresponds to a second group of documents.

6. The method of claim 1, wherein identifying a set of documents comprises:

determining an initial set of documents, and

generating a set of documents by expanding the initial set of documents based on documents that point to the initial set of documents or are pointed to by the initial set of documents.

7. The method of claim 6, wherein determining whether the first and second documents are similar is further based on whether there exists a third document, which is not included in the set of documents, that points to both the first and second documents.

8. The method of claim 1, further comprising:

receiving a search query; and

wherein identifying a set of documents includes;

locating a set of documents based on the search query.

9. The method of claim 8, further comprising:

presenting the first and second documents as a group in a search result document.

10. The method of claim 9, wherein presenting the first and second documents as a group includes:

visually separating the group formed from the first and second documents from another group within the search result document.

11. The method of claim 1, wherein determining whether first and second documents in the set of documents are similar comprises:

determining a value based on a number of documents that point to both the first and second documents and the number of back links associated with the first and second documents; and

normalizing the value to determine whether the first and second documents are similar.

12. The method of claim 1, wherein determining whether first and second documents in the set of documents are similar includes:

determining a value based on the number of documents that point to both the first and second documents and the number of back links associated with the first and second documents, and

determining whether the first and second documents are similar based on the determined value.

13. The method of claim 1, wherein determining whether first and second documents in the set of documents are similar comprises:

determining a first value based on a number of documents that point to both the first and second documents and the number of back links associated with the first and second documents;

determining a second value based on the number of the back links associated with the first and second documents; and

dividing the first value by the second value to determine whether the first and second documents are similar.

14. A computer system, comprising:

means for identifying a set of documents;

means for determining whether first and second documents in the set of documents relate to a similar topic based on a number of documents that simultaneously point to both the first and second documents and a number of back links associated with the first and second documents, wherein a result of the determination of whether the first and second documents relate to a similar topic is inversely proportional to the number of back links associated with the first and second documents; and

means for grouping the first and second documents when the first and second documents are determined to relate to a similar topic.

15. The computer system of claim 14, wherein the means for determining whether first and second documents in the set of documents relate to a similar topic includes:

means for determining a numerical value based on the number of documents that point to both the first and second documents and the number of back links associated with the first and second documents, and

determining whether the first and second documents relate to a similar topic based on the determined numerical value.

16. An automated method, comprising:

identifying a set of documents;

identifying each of the documents in the set of documents as a separate group;

determining whether to merge two of the groups based on a number of documents that point to documents in both of the two groups and a number of back links associated with the two groups, where a result of the determination of whether to merge the two groups is inversely proportional to the number of back links associated with the two groups; and

merging the two groups when it is determined that the two groups should be merged.

17. An automated method, comprising:

identifying a set of documents;

identifying each of the documents in the set of documents as a separate group;

determining whether two of the groups relate to a similar topic based on a number of documents that point to documents in both of the two groups and a number of back links associated with the two groups, where a result of the determination of whether the two groups relate to a similar topic is inversely proportional to the number of back links associated with the two groups; and

merging the two groups when it is determined that the two groups relate to a similar topic.

18. The method of claim 17, further comprising:

determining whether another group relates to a same topic as the merged group based on a number of documents that point to documents in both the other group and the merged group; and

merging the other group with the merged group when the other group is determined to relate to the same topic as the merged group.

19. The method of claim 17, wherein determining whether the two groups relate to a similar topic is based on subtracting a product of the number of back links associated with each of the two groups from the number of documents that point to documents in both of the two groups.

20. The method of claim 17, further comprising:

repeating the determining and the merging for additional groups of documents.

21. The method of claim 17, wherein determining whether two of the groups relate to a similar topic includes:

determining a value based on the number of documents that point to documents in both of the two groups and the number of back links associated with the two groups, and

determining whether the two groups relate to a similar topic based on the determined value.

22. A system, comprising:

a memory to store instructions; and

a processor to execute the instructions in the memory to;

identify a set of documents,

identify the documents in the set of documents as separate groups,

determine whether two of the groups relate to a similar topic based on a number of documents that simultaneously point to documents in both of the two groups and a number of back links associated with the two groups, where a result of the determination of whether the two groups relate to a similar topic is inversely proportional to the number of back links associated with the two groups, and

merge the two groups when it is determined that the two groups relate to a similar topic.

23. The system of claim 22, wherein when determining whether two of the groups relate to a similar topic, the processor is configured to:

determine a value based on the number of documents that simultaneously point to documents in both of the two groups and the number of back links associated with the two groups, and

determine whether the two groups relate to a similar topic based on the determined value.

24. An automated method, comprising:

receiving a search query;

identifying a set of documents based on the search query;

forming groups from documents in the set of documents based on a function that receives as inputs a number of documents that point to pairs of the documents in the set of documents and a number of back links associated with the documents in the set of documents, where a result of the function is inversely proportional to the number of back links associated with the documents;

generating a search result document in which at least one of the groups is visually separated from another one of the groups; and

presenting the search result document.

25. The method of claim 24, wherein generating a search result document includes:

providing information regarding less than all of the documents in one or more of the groups within the search result document.