Method of constant interaction-time clustering applied to document browsing

• US 5,483,650 A
• Filed: 06/21/1993
• Issued: 01/09/1996
• Est. Priority Date: 11/12/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Karger, David R., Cutting, Douglass R., Pedersen, Jan O.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/079,292
• Time in Patent Office: 932 Days
• Field of Search: 395/600, 395/144, 395/140, 395/141, 364/419.13, 364/419.19, 364/401, 364/225.6, 382/39, 340/146.2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Arbitrarily large document collections are processed by expanding a focus set having at least one initial metadocument into a plurality of subsequent metadocuments. The number of subsequent metadocuments is approximately equal to a predetermined maximum number. The subsequent metadocuments are then clustered into a predetermined number of new metadocuments, which are summarized and presented to a user. The focus set is redefined to include only user-selected new metadocuments.

Claims

1. A method of processing a corpus of electronically stored documents, comprising the steps of:

expanding a focus set comprised of at least one initial metadocument, representative of a plurality of documents, into a plurality of subsequent metadocuments, a number of said subsequent metadocuments being approximately equal to a predetermined maximum number, said subsequent metadocuments being descendants of said at least one initial metadocument in a tree, said expanding step comprising,

choosing a metadocument in the focus set that represents the most individual documents, and

expanding the chosen metadocument into its descendant metadocuments; and

clustering the subsequent metadocuments into a predetermined number of new metadocuments. the predetermined number of new metadocuments being less than the predetermined maximum numbers; and

selecting the predetermined maximum number so that said expanding and clustering steps can be completed within a time constraint.

2. The method of claim 1, wherein said at least one initial metadocument is a single metadocument representative of said entire corpus of documents.

3. The method of claim 2, further including the step of creating said single metadocument by a partitional clustering method.

4. The method of claim 1, wherein said at least one initial metadocument is a plurality of metadocuments selected by a user.

5. The method of claim 1, wherein said descendant metadocuments descend immediately in the tree from the chosen metadocument.

6. The method of claim 1, further comprising the step of repeating the choosing step as long as the total number of metadocuments in the focus set does not exceed the predetermined maximum number.

7. The method of claim 1, wherein the clustering step takes a predetermined amount of time regardless of the number of documents represented by each metadocument.

8. The method of claim 1, further comprising the steps of:

determining a summary of the new metadocuments; and

presenting the summary to a user.

9. The method of claim 8, further comprising the step of redefining the focus set to include only user-selected new metadocuments.

10. The method of claim 8, wherein the summary includes:

a fixed number of topical words that occur most often in each new metadocument; and

the title of at least one typical document within each new metadocument.

11. The method of claim 10, wherein each document and each new metadocument is represented by a set of word-frequency pairs, and the at least one typical document within each new metadocument is defined by determining which document or documents within each new metadocument are represented by a set of word-frequency pairs most similar to the set of word-frequency pairs that represents each respective new metadocument.

12. The method of claim 1, wherein each document is represented as a set of word-frequency pairs, and wherein each metadocument is represented as a set of word-frequency pairs determined from a sum of sets of word-frequency pairs of documents represented by the metadocument.

13. The method of claim 12, wherein the set of word-frequency pairs of each metadocument includes only pairs with the highest frequencies, such that the clustering step takes a predetermined amount of time regardless of the number of documents represented by each metadocument.