Link based clustering of hyperlinked documents

• US 8,516,357 B1
• Filed: 12/02/2010
• Issued: 08/20/2013
• Est. Priority Date: 08/12/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R.
• Primary Examiner(s): Hutton, Jr., Doug
• Assistant Examiner(s): Dasgupta, Soumya
• Application Number:
  US12/959,141
• Time in Patent Office: 992 Days
• Field of Search: 715/200, 715/206, 715/207, 715/208
• US Class Current: 715/200
• 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. A computer-implemented method, comprising:

identifying, by a device, a set of documents;

expanding, by the device, the set of documents to generate an expanded set of documents,

where the expanded set of documents includes all of the documents in the set of documents and one or more additional documents, and

where each additional document, of the one or more additional documents, links to a document in the set of documents or is linked to by a document in the set of documents;

determining, by the device, a similarity measure for each pair of documents in the expanded set of documents,

where, for a pair of documents, in the expanded set of documents, consisting of a first document and a second document, the similarity measure is determined based on;

a quantity of documents in the expanded set of documents that contain both a forward link to the first document and a forward link to the second document,

whether the first document contains a forward link to the second document, and

whether the second document contains a forward link to the first document; and

clustering, by the device, the documents in the expanded set of documents into a plurality of clusters based on the similarity measures.

2. The computer-implemented method of claim 1, where the similarity measure, for the pair of documents, is determined further based on an inverse of the quantity of documents that contain both the forward link to the first document and the forward link to the second document.

3. The computer-implemented method of claim 1, where the similarity measure, for the pair of documents, is further determined based on a measure of popularity of the first document and a measure of popularity of the second document.

4. The computer-implemented method of claim 3, where the measure of popularity of the first document is determined based on a quantity of documents, in the expanded set of documents, that link to the first document.

5. The computer-implemented method of claim 3, where the similarity measure, for the pair of documents, is determined further based on normalizing a value derived from the quantity of documents that contain both the forward link to the first document and the forward link to the second document, and

where the value is normalized based on the measure of popularity of the first document and the measure of popularity of the second document.

6. The computer-implemented method of claim 1, further comprising:

receiving a particular query as input to a search engine,

where each document in the set of documents is identified based on the particular query; and

presenting information regarding the documents, in the expanded set of documents, based on receiving the particular query,

where the information regarding the documents, in the expanded set of documents, is presented based on the plurality of clusters.

7. The computer-implemented method of claim 6, where presenting the information regarding the documents based on the plurality of clusters comprises:

visually separating the information regarding any documents in one of the plurality of clusters from the information regarding any documents in another one of the plurality of clusters.

8. The computer-implemented method of claim 1, where the documents, in the expanded set of documents, include web pages and the forward links include hyperlinks.

9. The computer-implemented method of claim 1, where clustering the documents comprises performing hierarchical clustering on the documents.

10. The computer-implemented method of claim 1, where clustering the documents comprises:

generating initial groups of documents, in the expanded set of documents, based on the similarity measures;

determining a group similarity measure for each pair of groups of documents in the initial groups of documents,

where, for a pair of groups of documents, in the initial groups of documents, consisting of a first group of documents and a second group of documents, the group similarity measure is determined based on a quantity of documents, in the expanded set of documents, that contain a forward link to a document in the first group of documents and contain a forward link to a document in the second group of documents; and

clustering the initial groups of documents based on the group similarity measures.

11. A system, comprising:

a memory to store instructions; and

a processor to execute the instructions to;

identify a plurality of documents;

expand the identified plurality of documents to generate an expanded plurality of documents,

where the expanded plurality of documents includes an entirety of documents in the identified plurality of documents and one or more additional documents, and

where each additional document, of the one or more additional documents, links to a document in the identified plurality of documents or is linked to by a document in the identified plurality of documents;

determine a similarity measure for each pair of documents in the expanded plurality of documents,

where, for a pair of documents, in the expanded plurality of documents, that includes a first document and a second document, the similarity measure is determined based on

a quantity of documents, in the expanded plurality of documents, that contain both a forward link to the first document and a forward link to the second document,

whether the first document contains a forward link to the second document, and

whether the second document contains a forward link to the first document; and

group, based on the similarity measures, documents, included in the expanded plurality of documents, into clusters to form clustered documents.

12. The system of claim 11, where the processor is further to:

receive a query,

where the plurality of documents are identified based on the query; and

present, based on receiving the query and based on the clusters, information regarding the clustered documents.

13. The system of claim 12, where, when presenting the information regarding the clustered documents, the processor is further to:

visually distinguish documents, included in a first one of the clusters, from documents, included in a second one of the clusters,

where the first one of the clusters is different from the second one of the clusters.

14. The system of claim 11, where the documents, included in the expanded plurality of documents, include web documents, and

where the forward links include hyperlinks.

15. The system of claim 11, where, when grouping the documents into clusters, the processor is further to:

generate, based on the similarity measures, groups of documents in the expanded plurality of documents,

determine a group similarity measure for each pair of groups of documents, in the generated groups of documents,

where, for a pair of groups of documents, in the generated groups of documents, that includes a first group of documents and a second group of documents, the group similarity measure is determined based on a quantity of documents, in the expanded plurality of documents, that include a forward link to a document in the first group of documents and contain a forward link to a document in the second group of documents; and

cluster the generated groups of documents based on the group similarity measures.

16. A non-transitory computer storage medium storing instructions, the instructions comprising:

one or more instructions which, when executed by one or more processors, cause the one or more processors to identify a plurality of documents;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to expand the identified plurality of documents to generate an expanded plurality of documents,

where the expanded plurality of documents includes an entirety of documents in the identified plurality of documents and one or more additional documents, and

where each additional document, of the one or more additional documents, links to a document in the identified plurality of documents or is linked to by a document in the identified plurality of documents;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine a similarity measure for each pair of documents in the expanded plurality of documents,

where, for a pair of documents, in the expanded plurality of documents, that includes a first document and a second document, the similarity measure is determined based on;

whether the first document contains a forward link to the second document,

whether the second document contains a forward link to the first document, and

a quantity of documents, in the expanded plurality of documents, that contain both a forward link to the first document and a forward link to the second document; and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to group, based on the similarity measures, documents, included in the expanded plurality of documents, into clusters to form clustered documents.

17. The non-transitory computer storage medium of claim 16, where the similarity measure, for the pair of documents, is determined based on an inverse of the quantity of documents that contain both the forward link to the first document and the forward link to the second document.

18. The non-transitory computer storage medium of claim 16, where the similarity measure, for the pair of documents, is determined further based on a measure of popularity of the first document and a measure of popularity of the second document, and

where the measure of popularity of the first document is determined based on a quantity of documents, in the expanded plurality of documents, that link to the first document.

19. The non-transitory computer storage medium of claim 16, where documents, included in the expanded plurality of documents, include web documents, and

where the forward links include hyperlinks.

20. The non-transitory computer storage medium of claim 16, the instructions further comprising:

one or more instructions which, when executed by the one or more processors, cause the one or more processors to present information regarding documents in the expanded plurality of documents,

where the one or more instructions to present the information regarding the documents comprise;

one or more instructions to visually separate the information regarding one or more of the documents in one of the clusters from the information regarding one or more of the documents in another one of the clusters.