Scatter-gather: a cluster-based method and apparatus for browsing large document collections

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.

Claims

What is claimed is:

1. A document browsing method in a digital computer for a corpus of documents, comprising the steps of:

preparing an initial ordering of the corpus into a first plurality of clusters by using a first method that automatically performs the initial ordering without external inputs based on contents of the documents using the digital computer;

determining a summary for each cluster of the first plurality of clusters prepared by said initial ordering of the corpus;

selecting by a user at least one cluster of the first plurality of clusters based on the summary of each cluster; and

automatically providing a further ordering of the user selected at least one cluster into a second plurality of clusters by automatically analyzing contents of documents of the selected at least one cluster using a second method comprising the steps of:

grouping together all of the documents from the selected at least one cluster based on the content of each document, and then

assigning each of the documents to one cluster of the second plurality of clusters.

2. The method of claim 1, wherein the preparing step includes a Fractionation method for partitioning the 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.

3. The method of claim 2, wherein the preparing an ordering step 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 corpus countfile;

adjoining the number of an earliest word in a sorted corpus countfile to a number of a first text-ordered word in the document to form a compound label; and

sorting documents by the compound label.

4. The method of claim 3, wherein the sorting words step further comprises:

segmenting the sorted corpus countfile according to frequency into a number of segments;

rearranging the sorted corpus countfile according to segments; and

renumbering words to reflect the rearranging.

5. The method of claim 2, wherein the 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.

6. The method of claim 2, wherein the refining step includes refining with a assign-to-nearest method for assigning a document to a nearest bucket.

7. The method of claim 2, wherein the refining step includes merging similar buckets.

8. The method of claim 2, wherein the refining step includes splitting non-similar buckets.

9. The method of claim 2, wherein the refining step includes detecting at least one of weak similarity and small buckets and incoherent buckets by applying size and average similarity thresholds.

10. The document partitioning method of claim 1, wherein 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.

11. The document partitioning method of claim 10, wherein the 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 .sqroot.kN 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.

12. The document partitioning method of claim 1, wherein the providing a further ordering step includes providing a further ordering step using a Buckshot method, said Buckshot method comprising the steps of:

constructing a random sample from the corpus of documents of size .sqroot.kN where k is an integer k 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 assign-to-nearest 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.

13. The document browsing method of claim 1, wherein the first method for preparing an initial ordering of the corpus is the same as the second method for providing a further ordering of a portion of the corpus.

14. A document browsing system for use with a corpus of documents in a digital computer, the document browsing system comprising:

preparing means for preparing without external inputs an initial ordering of the corpus into a first plurality of document clusters using the digital computer;

determining means for determining a summary for each cluster of the first plurality of document clusters prepared by said preparing means;

selecting means for a user to select at least one of the first plurality of document clusters; and

ordering means for automatically ordering the selected at least one of the first plurality of document clusters into a second plurality of clusters by

analyzing contents of documents of the selected at least one of the first plurality of document clusters,

grouping together all of the documents from the selected at least one of the first plurality of document clusters based on the contents of the documents of the selected at least one of the first plurality of document clusters, and then

assigning each of the documents to one cluster of the second plurality of clusters.

15. 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 by

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 corpus countfile,

adjoining the number of an earliest word in a sorted corpus countfile to a number of a first text-ordered word in the document to form a compound label, and

sorting documents by the compound label;

determining a partitioning of a desired size from the ordering to form a set of buckets, each document of the corpus of documents assigned to only one bucket of the set of buckets; and

refining the partitioning by a predetermined number of iterations of

creating a the set of modified buckets from the set of buckets based on contents and size of each bucket

reassigning each document of the corpus of documents to the set of modified buckets.

16. The Fractionation method of claim 14, wherein the sorting words step further comprises:

segmenting the sorted corpus countfile according to frequency into a number of segments;

rearranging the sorted corpus countfile according to segments; and

renumbering words to reflect the rearranging.

17. The Fractionation method of claim 14, wherein the determining 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.

18. The Fractionation method of claim 14, wherein the refining step includes refining with a assign-to-nearest method for assigning a document to a nearest bucket.

19. The Fractionation method of claim 14, wherein the refining step includes merging similar buckets.

20. The Fractionation method of claim 14, wherein the refining step includes splitting non-similar buckets.

21. The method of claim 14, wherein the refining step includes detecting at least one of weak similarity and small buckets and incoherent buckets by applying size and average similarity thresholds.

Description

BACKGROUND OF THE INVENTION

The present invention relates to a document-clustering-based browsing procedure for a corpus of documents, which is applicable over all natural languages that contain a lexical analysis capability.

Document clustering has been extensively investigated as methodology for improving document search and retrieval. The general assumption is that mutually similar documents will tend to be relevant to the same queries and hence, automatic determination of groups of such documents can improve recall by effectively broadening a search request. Typically a fixed corpus of documents is clustered either into an exhaustive partition, disjoint or otherwise, or into an hierarchical tree structure. In the case of a partition, queries are matched against clusters, and the contents of some number of the best scoring clusters are returned as a result, possibly sorted by score. In the case of a hierarchy, queries are processed downward, always taking the highest scoring branch, until some stopping condition is achieved. The subtree at that point is then returned as a result.

Hybrid strategies are also available, which are essentially variations of near-neighbor search, where nearness is defined in terms of the pairwise document similarity measure used to generate the clustering. Indeed, cluster search techniques are typically compared to similarity search, a direct near-neighbor search, and are evaluated in terms of precision and recall. Various studies have indicated that cluster search strategies are not markedly superior to similarity search and, in some situations, can be inferior. It is therefore not surprising that cluster search, given its indifferent performance, and the high determinable cost of clustering large corpora, has not gained wide popularity.

Document clustering has also been studied as a method for accelerating similarity search, but the development of fast procedures for near-neighbor searching has decreased interest in that possibility.

In order to cluster documents, one must first establish a pairwise measure of document similarity and then define a method for using that measure to form sets of similar documents, or clusters. Numerous document similarity measures have been proposed, all of which consider the degree of word overlap between the two documents of interest, described as sets of words, often with frequency information. These sets are typically represented as sparse vectors of length equal to the number of unique words (or types) in the corpus. If a word occurs in a document, its location in this vector is occupied by some positive value (one if only presence/absence information is considered, or some function of its frequency within that document if frequency is considered). If a word does not occur in a document, its location in this vector is occupied by zero. A popular similarity measure, the cosine measure, determines the cosine of the angle between these two sparse vectors. If both document vectors are normalized to unit length, this is of course, simply the inner product of the two vectors. Other measures include the Dice and Jaccard coefficient, which are normalized word overlap counts. It has also been suggested that the choice of similarity measure has less qualitative impact on clustering results than the choice of clustering procedure.

A wide range of clustering procedures have been applied to documents including, most prominently, single-linkage hierarchical clustering. Hierarchical clustering procedures proceed by iteratively considering all pairs of similarities, and fusing the pair which exhibits the greatest similarity. They differ in the procedure used to determine similarity when one of the pairs is a document group, i.e., the product of a previous fusion. Single-linkage clustering defines the similarity as the maximum similarity between any two individuals, one from each half of the pair. Alternative methods consider the minimum similarity (complete linkage), the average similarity (group average linkage), as well as other aggregate measures. Although single-linkage clustering is known to have an unfortunate chaining behavior, typically forming elongated straggly clusters, it continues to be popular due to its simplicity, and the availability of an optimal space/time procedure for its determination.

Standard hierarchical document clustering techniques employ a document similarity measure and consider the similarities of all pairs of documents in a given corpus. Typically, the most similar pair is fused and the process iterated, after suitably extending the similarity measure to operate on agglomerations of documents as well as individual documents. The final output is a binary tree structure that records the nested sequence of pairwise joints. Traditionally, the resulting trees had been used to improve the efficiency of standard boolean or relevance searches by grouping together similar documents for rapid access. The resulting trees have also lead to the notion of cluster search in which a query is matched directly against nodes in the cluster tree and the best matching subtree is returned. Counting all pairs, the cost of constructing the cluster trees can be no less than proportional to N.sup.2, where N is the number of documents in the corpus. Although clustering experiments have been conducted on corpora with documents numbering in the low tens of thousands, the intrinsic order of these clustering procedures works against the expectation that corpora will continue to increase in size. Similarly, although cluster searching has shown some promising results, the method tends to favor the most determinationally expensive similarity measures and seldom yields greatly increased performance over other standard methods.

Hierarchical methods are intrinsically quadratic in the number of documents to be clustered, because all pairs of similarities must be considered. This sharply limits their usefulness, even given procedures that attain this theoretical upper bound on performance. Partitional strategies (those that strive for a flat decomposition of the collection into sets of documents rather than a hierarchy of nested partitions) by contrast are typically rectangular in the size of the partition and the number of documents to be clustered. Generally, these procedures proceed by choosing in some manner, a number of seeds equal to the desired size (number of sets) of the final partition. Each document in the collection is then assigned to the closest seed. As a refinement the procedure can be iterated with, at each stage, a hopefully improved selection of cluster seeds. However, to be useful for cluster search the partition must be fairly fine, since it is desirable for each set to only contain a few documents. For example, a partition can be generated whose size is related to the number of unique words in the document collection. From this perspective, the potential determinable benefits of a partitional strategy are largely obviated by the large size (relative to the number of documents) of the required partition. For this reason partitional strategies have not been aggressively pursued by the information retrieval community.

The standard formulation of cluster search presumes a query, the user's expression of an information need. The task is then to search the collection of documents that match this need. However, it is not difficult to imagine a situation in which it is hard, if not impossible to formulate such a query. For example, the user may not be familiar with the vocabulary appropriate for describing a topic of interest, or may not wish to commit himself to a particular choice of words. Indeed, the user may not be looking for anything specific at all, but rather may wish to gain an appreciation for the general information content of the collection. It seems appropriate to describe this as browsing rather than search, since it is at one extreme of a spectrum of possible information access situations, ranging from requests for specific documents to broad, open-ended questions with a variety of possible answers. Standard information access techniques tend to emphasize search. This is especially clearly seen in cluster search where a technology capable of topic extraction, i.e., clustering, is submerged from view and used only as an assist for near-neighbor searching.

In proposing an alternative application for clustering in information access we take our inspiration from the access methods typically provided with a conventional text book. If one has a specific question in mind, and specific terms which define that question, one consults an index, which directs one to passages of interest, keyed by search words. However, if one is simply interested in gaining an overview, one can turn to the table of contents which lays out the logical structure of the text for perusal. The table of contents gives one a sense of the types of questions that might be answered if a more intensive examination of the text were attempted, and may also lead to specific sections of interest. One can easily alternate between browsing the table of contents, and searching the index.

By direct analogy, an information access system is proposed herein, which can have, for example, two components: a browsing tool which uses a cluster-based, dynamic table-of-contents metaphor for navigating a collection of documents; and one or more word-based, directed text search tools, such as similarity search, or the search technique described in U.S. patent application Ser. No. 07/745,794 to Jan O. Pedersen et al filed Aug. 16, 1991, and entitled An Iterative Technique For Phrase Query Formation and an Information Retrieval System Employing Same. The browsing tool describes groups of similar documents, one or more of which can be selected for further refinement. This selection/refinement process can be iterated until the user is directly viewing individual documents. Based on documents found in this process, or on terms used to describe document groups, the user may at any time switch to a more focused search method. In particular it is anticipated that the browsing tool will not necessarily be used to find particular documents, but may instead assist the user in formulating a search request, which will then be evaluated by some other means.

U.S. Pat. No. 4,956,774 to Shibamiya et al. discloses a method for selecting an access path in a relational database management system having at least one index. The first step is to select a number of most frequently occurring values of at least part of a key of the index. The number is greater than zero and less than the total number of such values. Statistics on the frequency of occurrence of the selected values are collected. An estimate of the time required to use the index as the access path is made, based at least in part on the index's most frequently occurring values statistics. The estimate is used as the basis at least in part for selecting an access path for the query. The database optimizer described is hierarchically organized in order of word frequency.

"Recent trends in hierarchic document clustering: A critical review" by Peter Willett, Information Processing of Management, Vol. 24, No. 5, pages 577-97 (1988--printed in Great Britain) describes the calculation of interdocument similarities and clustering methods that are appropriate for document clustering. The article further discusses procedures that can be used to allow the implementation of the aforementioned methods on databases of nontrivial size. The validation of document hierarchies is described using tests based on the theory of random graphs and on empirical characteristics of document collections that are to be clustered. A range of search strategies is available for retrieval from document hierarchies and the results are presented in a series of research projects that have used these strategies to search a cluster resulting from several different types of hierarchic agglomerative clustering methods. The article suggests that a complete linkage method is probably the most effective method in terms of retrieval performance; however, it is also difficult to implement in an efficient manner. Other applications of document clustering techniques are discussed briefly; experimental evidence suggests that nearest neighbor clusters, possibly represented as a network model, provide a reasonably efficient and effective means of including interdocument similarity information in document retrieval systems.

"Understanding Multi-Articled Documents" by Tsujimoto et al., presented in June 1990 in Atlantic City, N.J. at the 10th International Conference for Pattern Recognition, describes an attempt to build a method to understand document layouts without the assistance of character recognition results, i.e., the meaning of contents. It is shown that documents have an obvious hierarchical structure in their geometry which is represented by a tree. A small number of rules are introduced to transform the geometric structure into the logical structure which represents the semantics carried by the documents. A virtual field separator technique is employed to utilize information carried by a special constituent of documents such as field separators and frames, keeping the number of transformation rules small.

SUMMARY OF THE INVENTION

In the basic iteration of the proposed Scatter-Gather browsing tool, which can be defined as a method and apparatus for browsing large document collections, the user is presented with the descriptions (or summaries) of a fixed number of document groups. Based on these summaries, the user selects one or more of these groups for further study. These selected groups are gathered together to form a subcollection. The system then scatters (or reclusters) the new subcollection into the same fixed number of document groups, which are again presented to the user. With each successive iteration, since the number of documents decreases through selection while the number of groups remains fixed, the groups become smaller and therefore more detailed. Ultimately, when the groups become small enough, this process bottoms out by viewing individual documents. A history mechanism allows the user to backup from the results of an iteration, to either try a different selection or to backup further.

Scatter-Gather depends on the existence of two facilities. First, since clustering and reclustering is an essential part of the basic iteration, there is clearly a requirement for a procedure which can cluster a large number of documents within a time tolerable for user interaction (typically no more than about 60 seconds). For this strategy to scale with corpus size, some provision must also be made for dealing with corpora larger than can be clustered within this time allowance. Second, given a group of documents, some method for automatically summarizing the group must be specified. This cluster description must be sufficiently revealing for a user to gain a sense of the topic defined by the group, yet short enough for many descriptions to be appreciated simultaneously.

Three procedures are disclosed which can be used together to satisfy the above requirements, or used separately to enhance other corpus partitioning and/or searching techniques. A first procedure, Buckshot is a very fast partition-type clustering method suitable for an online reclustering preferable for Scatter-Gather. The Buckshot procedure employs three subprocedures. The first subprocedure is truncated group average agglomerative clustering which merges disjoint document sets, or groups, starting with individuals, until only a predetermined number of groups remain. At each step the two groups whose merger would produce the greatest average similarity are merged into a single new group. The second subprocedure determines a trimmed sum profile from selected documents closest to a document group centroid. The third subprocedure assigns individual documents to the closest center represented by one of the trimmed average profiles.

A second procedure, Fractionation, is another more precise, partition-type clustering method suitable for a static off-line partitioning of the entire corpus which can be presented first to the user. Fractionation can be thought of as a more careful version of Buckshot that trades speed for increased accuracy. In particular, the random sampling of a corpus of documents and the partitioning of the random sample by truncated group average agglomerative clustering (as provided in the Buckshot procedure), are replaced by a deterministic center finding subprocedure (for Fractionation). Fractionation also provides additional refinement iterations and procedures. Specifically, Fractionation provides initial partitioning of a corpus of documents using a deterministic center finding subprocedure. Then, by applying an Assign-to-Nearest subprocedure, a partition of a desired size is determined. Finally, the partitioning is refined through iterative refinement subprocedures.

A third procedure, Cluster Digest is a cluster summarization suitable as a cluster display method in Scatter-Gather. For Scatter-Gather, it is desirable for a summary to be constant in size, so a fixed number of summaries can be reliably fit onto a given display area. The Cluster Digest summary lists a fixed member of topical words plus the document titles of a few typical documents, where topical words are those that often occur in a cluster, and typical documents are those close to the cluster centroid (or trimmed centroid).

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described in detail with reference to the following drawings in which line reference numerals refer to like elements.

FIG. 1 is a block diagram of the hardware components used to practice the present invention.

FIG. 2 is a high level flowchart of a preferred embodiment of the Scatter-Gather document browsing method according to the present invention.

FIG. 3 is an illustrative diagram of a preferred embodiment of the Scatter-Gather document browsing method of the present invention being applied to a corpus of documents consisting of Grolier's Encyclopedia.

FIG. 4 is an intermediate level flowchart of a first embodiment of a Fractionation initial partitioning method of the present invention for preparing an initial ordering of a corpus of documents as used in the Scatter-Gather document browsing method.

FIG. 5 is a high level flowchart, according to the present invention, of an embodiment of a Cluster Digest method for determining a summary of an ordering of a corpus of documents in the Scatter-Gather document browsing method.

FIG. 6 is an intermediate level flowchart, according to the present invention, of a preferred embodiment of a Buckshot method for providing a further, preferably on-line, ordering of a corpus of documents in the Scatter-Gather browsing method.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A. Overview

The present invention can be implemented in a document corpus browsing system 12 as illustrated by block diagram in FIG. 1. The system includes a central processing unit (microprocessor) 1 for receiving signals from, and outputting signals to various other components of the system, according to one or more programs run on microprocessor 1. The system includes a read only memory (ROM) 2 for storing operating programs. A random access memory (RAM) 3 is provided for running the various operating programs, and additional files 4 could be provided for overflow and the storage of partitioned corpora used by the present invention in performing a search operation.

Prior to performing a browsing procedure, a document corpus is input from a corpus input 5. The corpus is then partitioned by software controlling processor 1 according to the teachings of the present invention.

Monitor 8 is provided for displaying results of partitioning procedures, and for permitting the user to interface with the operating programs. A user input device 9 such as, for example, a mouse, a keyboard, a touch screen or combinations thereof is provided for input of commands by the operator. A printer 10 can also be provided so that hard copies of documents, as well as print-outs containing Cluster Digest summaries, can be printed.

The system 12 is based in a digital computer which can implement an off-line preparation of an initial ordering using, for example, the Fractionation method disclosed herein. The system 12 also determines a summary of the initial ordering of the corpus which can be displayed to user via monitor 8 or printer 10 for user interaction. This summary can be determined by, for example, using the Cluster Digest method disclosed herein. After receiving appropriate instructions from a user via user input device 9, system 12 can perform a further ordering of the corpus using, for example, the on-line Buckshot method described herein.

An illustration of Scatter-Gather in operation is shown in FIG. 3. Here the text collection 20 is an online-version of Grolier's encyclopedia (roughly 64 Megabytes of ASCII text) with each of the twenty-seven thousand articles treated as a separate document. Suppose the user is interested in investigating the role of women in the exploration of space. Rather than attempting to express this information need as a formal query, the user instead selects a number of the top-level clusters referenced as 22A-I that, from their description, seem relevant to the topic of interest. In this case, the user selects the clusters 22A, 22C and 22H labelled "military history", "science and industry", and "American society" to form a reduced corpus 24 of the indicated subset of articles from Grolier's. (Note, the cluster labels are idealized in this illustration; the actual implementation produces cluster descriptions which are longer than would fit conveniently in this figure. However, the given labels are reasonable glosses of topics described by actual cluster summaries).

The reduced corpus is then reclustered on the fly to produce a new set of clusters 26A-J covering the reduced corpus 24. Since the reduced corpus contains a subset of the articles in Grolier's, these new clusters are at a finer level of detail than the top-level clusters. The user again selects clusters of interest. In this case, these include clusters 26E, 26G and 26H labeled "aviation", "engineering", and "physics". Again, a further reduced corpus 28 is formed and reclustered. The final set of clusters 30A-F includes clusters labeled for "military aviation", "Apollo program", "aerospace industry", "weather", "astronomy" and "civil aviation". At this stage the clusters are small enough for direct perusal via an exhaustive list of article titles. Assuming at least one article of interest is found, the user may find more articles of a similar nature in the same cluster, or may use a directed search method, based on the vocabulary of the found article or of the cluster description, to find additional articles.

The Scatter-Gather browsing technique can be demonstrated in more detail through the following sample session performed with a prototype implementation. The basic steps are illustrated in FIG. 2, with the output data (output via a monitor or printer) being illustrated below. The corpus is still Grolier's encyclopedia and the goal is to find documents discussing space explorers. To create the initial partition (Step 16), the Buckshot clustering method is first applied. Fractionation could also be used for this task, time permitting.

    __________________________________________________________________________
    > (setq first (time (outline (all-docs tdb))))
    cluster 27581 items
    global cluster 525 items . . .
    cluster sizes 38 29 45 42 41 46 26 124 115 19
    assign to nearest . . . done
    cluster sizes 1838 1987 3318 2844 2578 2026 1568 4511 5730 1181
    assign to nearest . . . done
    cluster sizes 1532 2206 3486 2459 2328 2059 1609 4174 6440 1288
    Cluster 0: Size: 1532. Focus articles: American music, music, history of;
    Ita
      focus terms: music, opus, composer, century, musical, play, dance,
    style, i
    Cluster 1: Size: 2206. Focus articles: Christianity; Germany, history o;
    church
      focus terms:church, king, roman, son, war, century, christian, emperor,
    jo
    Cluster 2: Size: 3486. Focus articles: French literature; English
    literature;
      focus terms:novel, trans, play, eng, writer, life, poet, american,
    poem, s
    Cluster 3: Size: 2459. Focus articles: education; university; graduate
    educate
      focus terms:university, study, school, state, american, theory,
    college, s
    Cluster 4: Size: 2328. Focus articles: plant; fossil record; mammal;
    growth; o
      focus terms:water, year, cell, area, animal, body, disease, human,
    develop
    Cluster 5: Size: 2059. Focus articles: bird; shorebirds; flower;
    viburnum; cac
      focus terms:specie, family, plant, flower, grow, genus, tree, leaf,
    white,
    Cluster 6: Size: 1609. Focus articles: radio astronomy; space
    exploration; sta
      focus terms:tight, star, earth, space, energy, surface, motion, line,
    fiel
    Cluster 7: Size: 4174. Focus articles: Latin American art; art; American
    art a
      focus terms:city, century, art, plant, build, center, style, bc,
    museum, d
    Cluster 8: Size: 6440. Focus articles: United States, his; United States;
    Euro
      focus terms; state, war, unite, year, government, world, american,
    area, ri
    Cluster 9: Size: 1288. Focus articles: chemistry, history; organic
    chemistry;
      focus terms:chemical, element, compound, metal, numb, atom, water,
    process
    real time 465953 msec
    __________________________________________________________________________

    __________________________________________________________________________
    > time (setq second (outline first 6 8 9)))
    cluster 9337 items
    global cluster 305 items . . .
    cluster sizes 23 11 19 31 18 57 38 48 21 39
    assign to nearest . . . done
    cluster sizes 706 298 679 630 709 1992 980 1611 1159 573
    assign to nearest . . . done
    cluster sizes 538 315 680 433 761 1888 1376 1566 1068 712
    Cluster 0: Size: 538. Focus articles: Liberal parties; political parties;
    Lab
      focus terms:party, minister, government, prime, leader, war, state,
    politi
    Cluster 1: Size: 315. Focus articles: star; astronomy and astr;
    extragalactic
      focus terms:star, sun, galaxy, year, earth, distance, light,
    astronomer, m
    Cluster 2: Size: 680. Focus articles: television; glass; aluminum; sound
    reco
      focus terms:process, metal, material, tight, type, mineral, color,
    device,
    Cluster 3: Size: 433. Focus articles: Laccadive Islands; French Southern
    an;
      focus terms:island, sq, area, population, south, west, state, coast,
    north
    Cluster 4: Size: 761. Focus articles: organic chemistry; chemistry,
    history;
      focus terms:chemical, element, compound, numb, atom, acid, reaction,
    water
    Cluster 5: Size: 1888. Focus articles: United States, his; Europe,
    history of;
      focus terms:war, state, world, unite, american, british, army,
    government,
    Cluster 6: Size: 1376. Focus articles: president of the U; Democratic
    party; b
      focus terms:state, president, law, court, year, unite, right, american,
    wa
    Cluster 7: Size: 1566. Focus articles: United States; North America;
    Australia
      focus terms:state, river, area, population, north, south, year, west,
    regi
    Cluster 8: Size: 1068. Focus articles: space exploration; radio
    astronomy; ele
      focus terms;energy, space, light, earth, particle, field, theory,
    motion,
    Cluster 9: Size: 712. Focus articles: corporation; monopoly and compe;
    govern
      focus terms:company, state, unite, product, billion, year, service,
    sale,
    real time 186338 msec
    __________________________________________________________________________

    __________________________________________________________________________
    > (time (setq third (outline second 1 8)))
    cluster 1383 items
    global cluster 117 items . . .
    cluster sizes 12 4 8 15 12 7 8 22 9 20
    move to nearest . . . done
    cluster sizes 172 63 70 236 76 131 75 198 124 238
    move to nearest . . . done
    cluster sizes 176 83 86 205 86 134 84 187 132 210
    Cluster 0: Size: 176. Focus articles: thermodynamics; light; energy;
    optics;
      focus terms:energy, heat, light, temperature, gas, wave, motion, air,
    pres
    Cluster 1: Size: 83. Focus articles: analytic geometry; line; geometry;
    coor
      focus terms:point, line, plane, angle, circle, geometry, coordinate,
    curve
    Cluster 2: Size: 86. Focus articles: radio astronomy; observatory, astro;
    te
      focus terms:telescope, observatory, radio, instrument, astronomy,
    light, s
    Cluster 3: Size: 205. Focus articles: solar system; Moon; planets;
    astronomy,
      focus terms:earth, sun, solar, planet, moon, satellite, orbit, surface,
    ye
    Cluster 4: Size: 86. Focus articles: radio, magnetism; circuit, electric;
    ge
      focus terms:field, frequency, magnetic, electric, electrical, wave,
    circui
    Cluster 5: Size: 134. Focus articles: nuclear physics; atomic nucleus;
    physic
      focus terms:particle, energy, electron, charge, nuclear, proton,
    radiation
    Cluster 6: Size: 84. Focus articles: measurements; units, physical;
    electroma
      focus terms:unit, value, measure, numb, measurement, function, equal,
    obje
    Cluster 7: Size: 187. Focus articles: space exploration; Space Shuttle;
    Soyuz
      focus terms:space, launch, fright, orbit, satellite, mission, rocket,
    eart
    Cluster 8: Size 132. Focus articles: physics, history o; Einstein,
    Albert; g
      focus terms;theory, physic, light, physicist, motion, einstein, law,
    parti
    Cluster 9: Size: 210. Focus articles: star; extragalactic syst; astronomy
    and
      focus terms:star, galaxy, light, year, sun, distance, mass, cluster,
    brigh
    real time 37146 msec
    __________________________________________________________________________

    __________________________________________________________________________
    > (time (setq fourth (outline third 7)))
    cluster 187 items
    global cluster 43 items . . .
    cluster sizes 1 2 4 1 1 15 1 11 2 5
    assign to nearest . . . done
    cluster sizes 1 6 20 5 2 79 1 47 4 22
    assign to nearest . . . done
    cluster sizes 1 9 22 8 2 69 1 46 4 25
    Cluster 0: Size: 1. Focus articles: Stealth
      focus terms:radar, bomber, aircraft, fly, stealth, shape, wing,
    replace, a
    Cluster 1: Size: 9. Focus articles: Juno; von Braun, Wernher; Jupiter;
    soun
      focus terms:rocket,space, missile, research, jupiter, redstone,
    satellite
    Cluster 2: Size: 22. Focus articles: rockets and missil; Atlas; Thor;
    Titan;
      focus terms:missile, rocket, launch, stage, kg, thrust, space,
    ballistic,
    Cluster 3: Size: 8. Focus articles: helicopter; VTOL; flight; jet
    propulsio
      focus terms:flight, engine, air, aircraft, rotor, helicopter, lift,
    speed,
    Cluster 4: Size: 2. Focus articles: STOL; C-5 Galaxy;
      focus terms:aircraft, wing, speed, lift, engine, air, takeoff, land,
    weigh
    Cluster 5: Size: 69. Focus articles: space exploration Soyuz; Salyut;
    Volko
      focus terms:space, launch, soyuz, cosmonaut, soviet, flight,
    spacecraft, m
    Cluster 6: Size: 1. Focus articles: railgun;
      focus terms:projectile, sec, accelerate, speed, space, test, launch,
    field
    Cluster 7: Size: 46. Focus articles: Gordon, Richard F.; Stafford, Thomas
    P;
      focus terms:astronaut, apollo, pilot, space, lunar, mission, flight,
    moon,
    Cluster 8: Size: 4. Focus articles: phobia; claustrophobia; agoraphobia;
    He
      focus terms;space, fear, phobia, claustrophobia, canvas, person,
    agoraphob
    Cluster 9: Size: 25. Focus articles: communications sat; GEOS; Vanguard;
    SYN
      focus terms:satellite, launch, orbit, space, earth, kg, communication,
    pro
    real time 18251 msec
    __________________________________________________________________________

    ______________________________________
           (print-titles (nth 5 fourth))
             40  Zond
             74  Zholobov, Vitaly
            238  Yelliseyev, Aleksei
                 Stanislavovich
            239  Yegorov, Boris B.
            921  weightlessness
            1269 Vostok
            1270 Voskhod
            1286 Volynov, Boris
                 Valentinovich
            1306 Volkov, Vladislav
                 Nikolayevich
            1574 Venera
            2345 tracking station
            2522 Titov, Gherman S.
            2881 Tereshkova, Valentina
            3959 Sputnik
            4120 Spacelab
            4125 space station
            4126 Space Shuttle
            4127 space medicine
            4128 space law
            4129 space exploration
            4131 Soyuz
            4365 SNAP
            4477 Skylab
            4849 Shatalov, Vladimir A.
            4943 Sevastianov, Vitaly I.
            5465 Sarafanov, Gennady
                 Vasilievich
            5611 Salyut
            5809 Ryumin, Valery
            5893 Rukavishnikov, Nikolay
            5928 Rozhdestvensky, Valery
            6074 Romanenko, Yury
                 Viktorovich
            6457 Remek, Vladimir
            6652 Ranger
            7381 Popovich, Pavel
                 Romanovich
            8267 Patsayev, Viktor
             9751
                 National Aeronautics and
                 Space Administration
           10915 Mercury program
           11104 McNair, Ronald
           11437 Mars
           11729 Makarov, Oleg
           12006 Lyakhov, Vladimir
           12042 Lunokhod
           12054 Luna (spacecraft)
           12616 Leonov, Aleksei
           12723 Lebedev, Valentin
           12766 Lazarev, V. G.
           13145 Kubasov, Valery N.
           13243 Komaraov, Vladimir
           13296 Klimuk, P. I.
           13427 Khrunov, Yevgeny
           13513 Kennedy, Space Center
           13626 Kapustin Yar (ka-poos-
                 tin yahr)
           14072 Jarvis, Gregory
           14224 Ivanov, Georgy
           14226 Ivanchenkov, Aleksandr
           16208 Gubarev, Aleksei
           16439 Grechko, Georgy
                 Mikhailovich
           16665 Gorbatko, Viktor V.
           16796 Godard Space Flight
                 Center
           16864 Glazkov, Yury
                 Nokolayevich
           18383 Feoktistov, Konstantin P.
           19449 Dzhanibekov, Vladimir
           19906 Dobrovolsky, Georgy T.
           20266 Demin, Lev Stepanovich
           23340 Bykovsky, Valery
           25920 astronautics
           26021 Artyukhin, Y. P.
           26313 Apollo-Soyuz Test Project
           27103 Aksenov, Vladimir
           (print title (nth 5 fourth))
            177  Young, John W.
            403  Worden, Alfred M.
            753  White, Edward H., II
            903  Weitz, Paul J.
            3391 Surveyor
            3910 Stafford, Thomas P.
            4460 Slayton, D. K.
            4805 Shepard, Alan B., Jr.
            5173 Scott, David R.
            5211 Schweickart, Russell L.
            5289 Schirra, Walter M., Jr.
            6047 Roosa, Stuart A.
            7519 Pogue, William Reid
           10526 Mitchell, Edgar D.
           11139 McDivitt, James
           11245 Mattingly, Thomas
           12050 Lunar Rover
           12051 Lunar Orbiter
           12052 Lunar Excursion Module
           12148 Lousma, Jack
           13897 Johnson Space Center
           14297 Irwin, James
           16026 Haise, Fred W.
           16299 Grissom, Virgil I.
           16651 Gordon, Richard F., Jr.
           16998 Gibson, Edward
           17189 Gemini program
           17282 Garriott, Owen
           18697 Evans, Ronald
           19236 Eisele, Donn F.
           19579 Duke, Charles, Jr.
           20916 Crippen, Robert
           21243 Cooper, Leroy Gordon, Jr.
           21348 Conrad, Pete
           21593 Collins, Michael
           22479 Chaffee, Roger
           22523 Cernan, Eugene
           22826 Carr, Gerald
           22835 Carpenter, Scott
           23924 Brand, Vance
           25140 Bean, Alan
           25921 astronaut
           26102 Armstrong, Neil A.
           26314 Apollo program
           26567 Anders, William Alison
           26998 Aldrin, Edwin E.
    ______________________________________

• Inventors
  Pedersen, Jan. O.; Karger, David; Cutting, Douglass R.; Tukey, John W.;
• Assignee
  Xerox Corporation (Stamford, CT)
• Published
  Aug-15-1995
• Current US Classes:
  707/5
  707/7
• Application #
  790316
• International Classes
  G06F 017/30
• Field of Search
  395/600 395/144 382/39 340/146.2 364/419.19 364/419.13
• Examiner
  Black; Thomas G.
• Agent
  Oliff & Berridge
• US Patent References:
  4053871
  4575798
  4774655
  4774657
  4956774
  4972349
  5075896
  5168565
  5257365
  5278980