Clustering documents using citation patterns

• US 8,612,411 B1
• Filed: 12/31/2003
• Issued: 12/17/2013
• Est. Priority Date: 12/31/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mittal, Vibhu O.
• Primary Examiner(s): Pulliam, Christyann
• Assistant Examiner(s): ADAMS, CHARLES D
• Application Number:
  US10/750,186
• Time in Patent Office: 3,639 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6, 707/102, 707/706, 707/739, 707/750, 707705-709, 707999001-99901, 715/513
• US Class Current: 707/706
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems and methods for clustering documents, such as for scientific documents, taking into account the citation patterns of the documents are disclosed. In one embodiment, the method includes locating citations to other documents, e.g., search result documents, comparing each pair of documents to be clustered for overlapping citations in a first, a more specific second, and an even more specific optional third citation generality, and determining clusters of related documents based on the comparisons. The levels of generalities may be, for example, document-, paragraph-, and/or citation-level generalities. The locating may locate only citations to the other documents to be clustered. The clusters may be determined based on a weighted score of the amount of overlapping citations in the various generalities and/or by performing factor analysis using the comparison results. The clusters may be ranked to determine the dominant clusters.

Claims

1. A method for clustering documents using one or more processors, the method comprising:

in each document in a collection of documents, locating citations, the citations including references to other documents;

for each pair of one or more pairs of documents in the collection of documents, performing actions comprising;

comparing the pair of documents based on overlapping citations at a first document structure level to generate a first citation overlap level, each of the overlapping citations at the first citation overlap level including common references to a same other document, the common references occurring at the first document structure level in each document of the pair;

comparing the pair of documents based on overlapping citations at a second document structure level to generate a second citation overlap level, each of the overlapping citations at the second citation overlap level including common references to a same other document, the common references occurring at the second document structure level in each document of the pair, where the second document structure level is more specific than the first document structure level; and

combining the first citation overlap level and the second citation overlap level to generate a citation overlap score for the pair of documents;

determining a plurality of clusters of related documents in the collection of documents according to the citation overlap scores;

ranking the plurality of clusters including;

generating a weighted cluster citation overlap score for each pair of documents in each cluster of the plurality of clusters, and

penalizing the weighted cluster citation overlap score for one or more clusters based on whether each cluster contains documents that contain only overlapping citations with other documents at the first document structure level;

and

providing a listing of the plurality of clusters of related documents based on the ranking.

2. The method of claim 1, wherein the actions comprise comparing the pair of documents based on overlapping citations on a third document structure level, the third document structure level being more specific than the second document structure level.

3. The method of claim 1, further comprising:

generating search results including a plurality of search result documents, the documents in the collection of documents being selected from the plurality of search result documents.

4. The method of claim 1, wherein the locating comprises locating only citations to the other documents in the collection of documents.

5. The method of claim 1, wherein the first and second document structure levels are selected from the group consisting of a document level, a paragraph level, a citation level, a page level, a chapter level, a section level, a subsection level, a sentence level, a multiple sentence level, and a word distance level.

6. The method of claim 1, further comprising:

determining a weighted citation overlap score based on an amount of overlapping citations at the first and second document structure levels.

7. The method of claim 6, wherein in determining the weighted citation overlap score, the amount of overlapping citations at the second document structure level is weighted more heavily than the amount of overlapping citations at the first document structure level.

8. The method of claim 1, wherein the determining comprises:

performing factor analysis using results from the comparisons.

9. The method of claim 8, wherein the factor analysis is selected from the group comprising principal component analysis (PCA) and principal factor analysis (PFA).

10. The method of claim 1, wherein ranking the plurality of clusters

includes determining one or more dominant clusters based on a cluster score, the cluster score being based on results of the comparisons.

11. A system comprising:

one or more computers configured to perform operations comprising;

in each document in a collection of documents, locating citations, the citations including references to other documents;

for each pair of one or more pairs of documents in the collection of documents, performing actions comprising;

comparing the pair of documents based on overlapping citations at a first document structure level to generate a first citation overlap level, each of the overlapping citations at the first citation overlap level including common references to a same other document, the common references occurring at the first document structure level in each document of the pair;

comparing the pair of documents based on overlapping citations at a second document structure level to generate a second citation overlap level, each of the overlapping citations at the second citation overlap level including common references to a same other document, the common references occurring at the second document structure level in each document of the pair, where the second document structure level is more specific than the first document structure level; and

combining the first citation overlap level and the second citation overlap level to generate a citation overlap score for the pair of documents;

determining a plurality of clusters of related documents in the collection of documents according to the citation overlap scores;

ranking the plurality of clusters including;

generating a weighted cluster citation overlap score for each pair of documents in each cluster of the plurality of clusters, and

penalizing the weighted cluster citation overlap score for one or more clusters based on whether each cluster contains documents that contain only overlapping citations with other documents at the first document structure level; and

providing a listing of the plurality of clusters of related documents based on the ranking.

12. The system of claim 11, wherein the actions comprise comparing the pair of documents based on overlapping citations in a third document structure level, the third document structure level being more specific than the second document structure level.

13. The system of claim 11, the operations further comprising generating search results including a plurality of search result documents, the documents in the collection of documents being selected from the search result documents.

14. The system of claim 11, wherein the locating comprises locating only citations to the other documents in the collection of documents.

15. The system of claim 11, wherein the first and second document structure levels are selected from the group consisting of a document level, a paragraph level, a citation level, a page level, a chapter level, a section level generality, a subsection level, a sentence level, a multiple sentence level, and a word distance level.

16. The system of claim 11, the operations further comprising determining a weighted citation overlap score based on an amount of overlapping citations at the first and second document structure levels.

17. The system of claim 16, wherein in determining the weighted citation overlap score, the amount of overlapping citations at the second document structure level is weighted more heavily than the amount of overlapping citations in the first document structure level.

18. The system of claim 11, wherein the determining comprises performing factor analysis using results from the comparisons.

19. The system of claim 18, wherein the factor analysis is selected from the group comprising principal component analysis (PCA) and principal factor analysis (PFA).

20. The system of claim 11, wherein ranking the plurality of clusters includes determining one or more dominant clusters based on a cluster score, the cluster score being based on results of the comparisons.

21. A computer program product embodied on a non-transitory computer-readable medium, the computer program product including instructions, which when executed by a computer system, are configured to cause the computer system to perform operations comprising:

in each document in a collection of documents, locating citations, the citations including references to other documents;

for each pair of one or more pairs of documents in the collection of documents, performing actions comprising;

comparing the pair of documents based on overlapping citations at a first document structure level to generate a first citation overlap level, each of the overlapping citations at the first citation overlap level including common references to a same other document, the common references occurring at the first document structure level in each document of the pair;

comparing the pair of documents based on overlapping citations at a second document structure level to generate a second citation overlap level, each of the overlapping citations at the second citation overlap level including common references to a same other document, the common references occurring at the second document structure level in each document of the pair, where the second document structure level is more specific than the first document structure level; and

combining the first citation overlap level and the second citation overlap level to generate a citation overlap score for the pair of documents;

determining a plurality of clusters of related documents in the collection of documents according to the citation overlap scores;

ranking the plurality of clusters including;

generating a weighted cluster citation overlap score for each pair of documents in each cluster of the plurality of clusters, and

penalizing the weighted cluster citation overlap score for one or more clusters based on whether each cluster contains documents that contain only overlapping citations with other documents at the first document structure level; and

providing a listing of the plurality of clusters of related documents based on the ranking.

22. The computer program product of claim 21, wherein the actions comprise comparing the pair of based on overlapping citations in a third document structure level, the third document structure level being more specific than the second document structure level.

23. The computer program product of claim 21, further comprising instructions configured to cause the computer system to perform operations comprising:

generating search results including a plurality of search result documents, the documents in the collection of documents being selected from the plurality of search result documents.

24. The computer program product of claim 21, wherein the locating comprises locating only citations to the other documents in the collection of documents.

25. The computer program product of claim 21, wherein the first and second document structure levels are selected from the group consisting of a document level, paragraph level, a citation level, a page level, a chapter level, a section level, a subsection level, a sentence level, a multiple sentence level, and a word distance level.

26. The computer program product of claim 21, further comprising instructions configured to cause the computer system to perform operations comprising:

determining a weighted citation overlap score based on an amount of overlapping citations at the first and second document structure levels.

27. The computer program product of claim 26, wherein in determining the weighted citation overlap score, the amount of overlapping citations at the second document structure level is weighted more heavily than the amount of overlapping citations at the first document structure level.

28. The computer program product of claim 21, wherein the determining comprises:

performing factor analysis using results from the comparisons.

29. The computer program product of claim 28, wherein the factor analysis is selected from the group comprising principal component analysis (PCA) and principal factor analysis (PFA).

30. The computer program product of claim 21, wherein ranking the plurality of clusters

includes determining one or more dominant clusters based on a cluster score, the cluster score being based on results of the comparisons.