EP0542429A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A cluster-based method and system for browsing large document collections
Assignee: Xerox Corp
•
Filing: 1992-10-15
•
Granted: —
•
Expires: 2012-10-15
Abstract
Abstract Scatter-Gather is a computer based document browsing method which operates in time proportional to a number of documents in a target corpus. The Scatter-Gather method includes: preparing an initial ordering of the corpus using, for example, an off-line computational method; determining a summary of the initial ordering of the corpus for interactive utility; and providing a further ordering of the corpus using, for example, an on-line non-deterministic method. The step of an off-line preparation of an initial ordering of a corpus is non- time-dependent, thus an accurate initial ordering is prepared. The step of determining a summary includes determining a summary for presentation to a user without scrolling on a CRT. The step of providing a further ordering includes truncated group average agglomerate clustering, merging disjointed document sets, center finding, assign-to-nearest and other refinement methods.
Inventors
- 👤 Jan O. Pedersen
- 👤 John W. Tukey
- 👤 David Karger
- 👤 Douglass R. Cutting
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 21:20
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/99933; Y10S707/99935; Y10S707/99937
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
80 words
A document browsing method in a digital computer for a corpus of documents, characterised by preparing an initial ordering of the corpus into a plurality of clusters, using an off-line method; determining a summary of the plurality of clusters prepared by said initial ordering of the corpus, for on-line user interaction; and providing a further ordering of a portion of the corpus using an on-line method, said portion of the corpus corresponding to user selected clusters from said initial ordering.
Claim 2
Dependent Claim
48 words
A method as claimed in claim 1, characterised in that preparing an initial ordering includes a Fractionation method for partitioning the corpus of documents, said Fractionation method including preparing an ordering of the corpus; determining a partitioning of a desired size from the ordering; and refining the partitioning.
Claim 3
Dependent Claim
82 words
A method as claimed in claim 2, characterised in that preparing the ordering of the corpus includes: sorting words in order of frequency, most frequent word first, by entry into a corpus countfile; labeling each document by a number of an earliest word in a sorted file which appears in the sorted file; adjoining the number of an earliest word in a sorted file to a number of a first text-ordered word in the document; and sorting documents by a compound label.
Claim 4
Dependent Claim
44 words
A method as claimed in claim 3, characterised in that sorting words in order of frequency further comprises: segmenting the sorted countfile according to frequency into a number of segments; rearranging the sorted countfile according to segments; and renumbering words to reflect the rearranging.
Claim 5
Independent Claim
47 words
A method as claimed in any one of claims 2 to 4, characterised in that determining a partition step comprises truncated group averaging agglomerative clustering which includes limiting a growth of an agglomeration by terminating a group averaging agglomerative clustering before a single over-arching agglomeration is formed.
Claim 6
Independent Claim
56 words
A method as claimed in any one of claims 2 to 5, characterised in that refining the partitioning includes refining with a assign-to-nearest method for assigning a document to a nearest bucket, or includes merging similar buckets, or includes splitting non-similar buckets, or includes detecting weak-small and incoherent buckets by applying size and two-way link thresholds.
Claim 7
Dependent Claim
89 words
A document partitioning method as claimed in any one of claims 1 to 6, characterised in that the determining a summary step includes determining a summary using a Cluster Digest method, said Cluster Digest method comprising the steps of: providing a summary of constant size for each cluster; and listing a fixed number of topical words plus document titles of a few typical documents within each cluster, wherein the topical words are words that occur often in the cluster and typical documents are documents close to a cluster centroid.
Claim 8
Dependent Claim
142 words
A document partitioning method as claimed in any one of claims 1 to 7, characterised in that providing a further ordering step includes providing a further ordering using a Buckshot method, said Buckshot method comprising the steps of: constructing a random sample from the corpus of documents of size where k is an integer number of desired clusters and N is a number of documents in the corpus of documents; partitioning into a partition G a random sample into k groups using truncated group average agglomerative clustering; constructing a partition P of the corpus of documents by assigning each document to a k center in partition G and applying an assign-to-nearest procedure over the corpus and the k centers in partition G; replacing partition G with partition P and repeating the step of constructing a partition; and returning a new partition P.
Claim 9
Dependent Claim
111 words
A document browsing system for use with a corpus of documents in a digital computer, the document browsing system including: initial ordering means (16) for off-line preparation of an initial ordering of the corpus into a plurality of document clusters; determine summary means (17) for determining a summary of the plurality of document clusters prepared by said off-line preparation means, said summary capable of being displayed to a user; and further ordering means (18), responsive to a user-input selection of some of said document clusters, for providing a further ordering of a portion of the corpus using an on-line method, said portion of the corpus corresponding to the user-selected document clusters.
Claim 10
Dependent Claim
45 words
A document partitioning Fractionation method in a digital computer for non-hierarchical, linear-time partitioning of a corpus of documents, said Fractionation method comprising the steps of: preparing an ordering of the corpus; determining a partitioning of a desired size from the ordering; and refining the partitioning.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.