Method and apparatus for clustering a collection of linked documents using co-citation analysis

• US 6,038,574 A
• Filed: 03/18/1998
• Issued: 03/14/2000
• Est. Priority Date: 03/18/1998
• Status: Expired due to Term

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Pirolli, Peter L., Pitkow, James E., Card, Stuart K., Mackinlay, Jock D.
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/044,693
• Time in Patent Office: 727 Days
• Field of Search: 707/513, 707/514, 707/907, 707/901, 707/100, 707/102
• US Class Current: 715/210
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The method and apparatus of the present invention generates clusters of documents in a collection of linked documents based on co-citation analysis. The frequency linkage is determined for each document in the collection. In other words, the number of times each document is linked to by another document in the collection is determined. Further, a minimum frequency linkage (link frequency threshold) is specified based on a predetermined minimum frequency of document linkage. Additionally, a list of pairs of documents that are linked to by the same document is created so that each of the pairs of documents has a count of the number of times (co-citation frequency) that they are both linked to by another document. Pairs of linked documents are clustered using a suitable co-citation technique.

Claims

1. A method for clustering documents contained in a collection of linked documents, said method comprising the steps of:

a) specifying a link frequency threshold, said link frequency threshold indicating a number of times a document is linked to from another document in said collection;

b) for each document in said collection, determining an associated link frequency;

c) discarding each document in said collection whose link frequency is lower than said link frequency threshold;

d) creating a co-citation list, said co-citation list comprised of pairs of documents that are linked to by the same document in said collection; and

e) performing a suitable clustering operation on said co-citation list to generate document clusters.

2. The method as recited in claim 1 wherein said suitable clustering operation is a transitive closure clustering operation.

3. The method as recited in claim 1 wherein said suitable clustering operation is a statistical clustering operation.

4. The method as recited in claim 3 wherein said step of creating a co-citation list is further comprised of the step of for each pair in said co-citation list, generating a co-citation frequency indicating the number of times each pair was cited by the same document, and wherein said statistical clustering operations uses said co-citation frequency.

5. The method as recited in claim 1 wherein said method is further comprised of the steps of:

f) determining if said generated document clusters provides acceptable clustering results;

g) if said generated document clusters does not provide acceptable clustering results, varying the value of said link frequency threshold; and

h) repeating steps b)-e).

6. The method as recited in claim 5 wherein an unacceptable clustering results is a combination of few large clusters and many small clusters, said step of varying the value of said link frequency threshold causes said link frequency threshold to decrease.

7. The method as recited in claim 5 wherein an unacceptable clustering result is a combination of fewer clusters with fewer documents in the clusters, said step of varying the value of said link frequency threshold causes said link frequency threshold to increase.

8. The method as recited in claim 5 wherein prior to step f) performing the step of presenting a visualization of said generated document clusters.

9. A system for clustering documents in a collection of linked documents, said system comprising

means for accessing said documents in said collection of linked documents;

means for specifying a link frequency threshold;

link analysis means for analyzing the links contained in said documents in said collection of linked documents, said link analysis means further comprising;

means for determining the number of times a document has been linked to; and

means for generating a co-citation list, said co-citation list indicating pairs of documents that have been linked to by the same document;

clustering means for generating document clusters from said co-citation list.

10. The system as recited in claim 9 wherein said clustering means performs a transitive closure operation.

11. The system as recited in claim 9 wherein said clustering means performs a statistical clustering operation.

12. The system as recited in claim 11 wherein said means for generating a co-citation list is further comprised of the step of generating a co-citation frequency for each pair in said list, said co-citation frequency indicating the number of times each of said pairs in said list were linked to by the same document, and said statistical clustering operation utilizes said co-citation frequency.

13. The system as recited in claim 9 further comprising cluster display visualization means for providing a visual display of said generated document clusters.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for the clustering of documents in a collection of linked documents, said method steps comprising:

a) specifying a link frequency threshold, said link frequency threshold indicating a number of times a document is linked to from another document in said collection;

b) for each document in said collection, determining an associated link frequency;

c) discarding each document in said collection whose link frequency is lower than said link frequency threshold;

d) creating a co-citation list, said co-citation list comprised of pairs of documents that are linked to by the same document in said collection; and

e) performing a suitable clustering operation on said co-citation list to generate document clusters.

15. The program storage device as recited in claim 14 wherein said method steps are further comprised of the steps of:

f) displaying a visualization of said document clusters;

g) determining if said generated document clusters provides acceptable clustering results;

h) if said generated document clusters does not provide acceptable clustering results, varying the value of said link frequency threshold; and

i) repeating steps b)-f).