US5483650A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of constant interaction-time clustering applied to document browsing
Assignee: Xerox Corp
•
Filing: 1993-06-21
•
Granted: 1996-01-09
•
Expires: 2013-06-21
Abstract
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.
Inventors
- 👤 Jan O. Pedersen
- 👤 David R. Karger
- 👤 Douglass R. Cutting
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 23:00
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/355; G06F16/90; G06F16/93; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
137 words
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.
Claim 2
Independent Claim
137 words
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.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein said at least one initial metadocument is a single metadocument representative of said entire corpus of documents.
Claim 4
Dependent Claim
19 words
The method of claim 2, further including the step of creating said single metadocument by a partitional clustering method.
Claim 5
Dependent Claim
21 words
The method of claim 1, wherein said at least one initial metadocument is a plurality of metadocuments selected by a user.
Claim 6
Dependent Claim
18 words
The method of claim 1, wherein said descendant metadocuments descend immediately in the tree from the chosen metadocument.
Claim 7
Dependent Claim
33 words
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.
Claim 8
Dependent Claim
25 words
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.
Claim 9
Dependent Claim
24 words
The method of claim 1, further comprising the steps of: determining a summary of the new metadocuments; and presenting the summary to a user.
Claim 10
Dependent Claim
20 words
The method of claim 8, further comprising the step of redefining the focus set to include only user-selected new metadocuments.
Claim 11
Dependent Claim
36 words
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.
Claim 12
Dependent Claim
65 words
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.
Claim 13
Dependent Claim
43 words
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.
Claim 14
Dependent Claim
42 words
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.
References Cited (Backward Citations)
US495674A
Cited
US4972349A
Cited
US5168565A
Cited
US5179643A
Cited
US5075896A
Cited
US5257365A
Cited
US5325298A
Cited
US5278980A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-08 | 1999-07-10 | 2000-01-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-08 | 2003-07-10 | 2004-01-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-08 | 2007-07-10 | 2008-01-09 | $7700.00 | Window Closed / Lapsed |