Scatter/Gather: a cluster-based approach to browsing large document collections

Douglass R. CuttingJan O. PedersenDavid R KargerJohn W. Tukey

article1992SIGIR1,869 citations

Introduces Scatter/Gather, an interactive information access paradigm paired with linear-time clustering algorithms that allows users to explore large document collections through iterative topic-based summarization rather than traditional keyword queries.

Listen

Traditional information retrieval systems rely heavily on keyword queries, which assume users know precisely what terms to search for. When users have vague information goals or lack familiarity with the vocabulary of a large text collection, standard keyword searches often fail. Historical attempts to apply document grouping to search were hindered by slow processing speeds and minimal retrieval improvements when forced into traditional search frameworks.

The article demonstrates an interactive browsing technique called Scatter/Gather and evaluates fast grouping procedures that make dynamic exploration feasible. Rather than using automated grouping merely to accelerate standard keyword searches, the authors propose using it as an intuitive, dynamic table-of-contents metaphor for navigating large text collections.

To evaluate this framework, the authors developed two linear-time grouping procedures—one tailored for fast interactive updates and another for more accurate initial corpus organization—and tested them on an experimental dataset of approximately 5,000 news articles. The interactive interface automatically generates concise summaries for each cluster using representative titles and high-frequency terms, allowing users to select subsets of interest and dynamically re-cluster them.

The investigation produced several key findings. First, localizing grouping operations to small sample sets or bounded partitions reduces computational processing time from quadratic to linear time, allowing interactive responses in seconds. Second, the faster sampling-based grouping procedure reliably identifies natural topic groups with high probability when document collections contain distinct subject areas. Third, dynamic re-clustering enables users to quickly isolate broad themes and drill down into obscure, localized stories that would otherwise remain hidden under broader subjects without requiring specific search keywords.

These findings indicate that content grouping can serve as an effective standalone discovery tool, reducing the cognitive effort and time needed to explore unfamiliar document archives. Instead of replacing standard keyword search, this browsing model complements focused lookup tools by helping users understand the thematic structure of a corpus and formulate better targeted queries.

For future implementation, the authors recommend combining offline structural preprocessing with fast sampling-based re-clustering during live user sessions. Because the interactive sampling procedure is non-deterministic and the browsing experience is exploratory, rigorous quantitative evaluation remains challenging until standardized metrics for open-ended browsing tasks are developed.

Palo Alto Research Center Princeton University Stanford University cluster head electronic document document clusters cluster search cluster digest

Cutting et al (1992).pdf

No sufficiently relevant recommendations were found.

Paper: Web document clustering: a feasibility demonstration, Oren Zamir et al. (1998). See how the cluster-browsing idea moves from document archives to live web search, where Suffix Tree Clustering organizes retrieved results for exploration.

Cover for Scatter/Gather: a cluster-based approach to browsing large document collections

Abstract

Document clustering has not been well received as an in- formation retrieval tool. Objections to its use fall into two main categories: first, that clustering is too slow for large corpora (with running time often quadratic in the number of documents); and second, that clustering does not appreciably improve retrieval.

We argue that these problems arise only when cluster- ing is used in an attempt to improve conventional search techniques. However, looking at clustering as an informa- tion access tool in its own right obviates these objections, and provides a powerful new access paradigm. We present a document browsing technique that employs document clustering as its primary operation. We also present fast (linear time) clustering algorithms which support this in- teractive browsing paradigm.

Topics

cluster head electronic document

Keywords

document clusters cluster search cluster digest online reclustering hierarchical clustering partitional clustering document similarity near-neighbor search

1 Introduction
1.1 Browsing vs Search
2 Scatter/Gather Browsing
2.1 An Illustration
2.2 Requirements
3 Document Clustering
4 Definitions
4.1 Cluster Digest
5 Partitional Clustering
5.1 Finding Initial Centers
Buckshot
Fractionation
5.2 Assigning Documents to Centers
5.3 Refinement
Iterated Assign-to-Nearest
Split
Join
6 Application to Scatter/Gather
6.1 Naturally Clustered Data
7 Conclusion
A A Scatter/Gather Session
B Group Average Clustering
References

Knowls

Knowl 1 — Scatter/Gather Document Browsing Paradigm
model/method
Scatter/Gather is an interactive information access method that employs document clustering as its primary navigational primitive, implementing a dynamic, cluster-based table-of-contents metaphor for navigating large, unstructured document collections without requiring prior knowledge of specific query keywords.

The interaction cycle operates iteratively as follows:
1. Scatter: The system clusters the current document collection (or subcollection) into a small number of document groups ( $k$ clusters) and presents concise, descriptive summaries (cluster digests) for each group to the user.
2. Gather: The user inspects the cluster summaries and selects one or more groups that appear relevant or interesting. The selected groups are aggregated to form a reduced subcollection.
3. Recluster: The system reclusters the reduced subcollection on the fly into $k$ new clusters, which expose a finer level of subtopical detail than previous iterations.
4. Iteration/Termination: Steps 1–3 repeat recursively until the clusters become sufficiently small that individual document titles or text passages can be enumerated directly, or until the user switches to a focused text search method (such as vector-space near-neighbor search or snippet search) using vocabulary learned during browsing.
Knowl 2 — Buckshot Fast Partitional Clustering Algorithm
algorithm
Buckshot is a randomized partitional clustering algorithm designed for fast, on-the-fly reclustering during interactive Scatter/Gather browsing. It achieves a rectangular time complexity of $O(kn)$ , where $n$ is the number of documents in the collection $C$ and $k$ is the target number of clusters.
Input: Document collection $C$ with $n = |C|$ , target cluster count $k$
Output: Disjoint partition $P = {\Gamma_1, \Gamma_2, \dots, \Gamma_k}$ of $C$
1. Draw a random sample $S \subset C$ of size $s = \sqrt{kn}$ uniformly without replacement
2. Cluster the sample $S$ into $k$ seed clusters $\{S_1, S_2, \dots, S_k\}$ using a high-quality agglomerative clustering subroutine (such as group-average agglomerative clustering)
3. Compute the normalized center profile for each seed cluster: $p(S_i) = \tilde{p}(S_i) / \|\tilde{p}(S_i)\|$ , where $\tilde{p}(S_i) = \sum_{\alpha \in S_i} p(\alpha)$
4. For each document $\alpha \in C$ :
Assign $\alpha$ to the cluster $\Gamma_i$ whose seed center $p(S_i)$ maximizes cosine similarity $s(\alpha, p(S_i))$ (breaking ties by lowest index)
5. Refine the partition by applying 2 iterations of Assign-to-Nearest using trimmed sum profiles $p_m(\Gamma_i)$
6. return $P = {\Gamma_1, \Gamma_2, \dots, \Gamma_k}$
Because finding seeds requires running the $O(s^2)$ agglomerative subroutine on $s = \sqrt{kn}$ documents, seed determination takes $O((\sqrt{kn})^2) = O(kn)$ time. Document assignment to the $k$ centers takes $O(kn)$ time, yielding an overall running time of $O(kn)$ .
Knowl 3 — Fractionation Linear-Time Clustering Algorithm
algorithm
Fractionation is a deterministic, hierarchical partitional clustering algorithm with $O(mn) = O(kn)$ time complexity, designed for high-accuracy offline initial partitioning of an entire document corpus prior to interactive browsing.
Input: Collection $C$ of $n$ documents, bucket size $m > k$ (with $m = O(k)$ ), reduction factor $\rho \in (0, 1)$ , target cluster count $k$ , sorting key index $j$ (e.g., $j = 3$ )
Output: Partition $P = {\Gamma_1, \Gamma_2, \dots, \Gamma_k}$ of $C$
1. Sort $C = (\alpha_1, \alpha_2, \dots, \alpha_n)$ based on the vocabulary index of the $j$ -th most frequent word in each document (placing documents with shared medium-frequency words near each other)
2. Set current collection $C' \leftarrow C$
3. while $|C'| > k$ and $|C'| / m \ge 1$ :
     Divide $C'$ into $\lfloor |C'| / m \rfloor$ contiguous buckets $B_1, B_2, \dots, B_{\lfloor |C'| / m \rfloor}$ of fixed size $m$
     For each bucket $B_i$ :
       Apply the agglomerative clustering subroutine to cluster the $m$ items of $B_i$ into $\lfloor \rho m \rfloor$ composite groups
     Set $C'$ to be the set of all newly formed composite groups, ordered lexicographically by bucket index and intra-bucket group index
4. Apply the agglomerative clustering subroutine to the remaining groups in $C'$ to reduce them to exactly $k$ groups
5. Treat the $k$ groups as seeds, compute center profiles, assign every document in $C$ to its nearest center, and apply partition refinement
6. return $P = {\Gamma_1, \Gamma_2, \dots, \Gamma_k}$
Each iteration $j$ operates on $\rho^j n$ items in time $\rho^j nm$ . Summing across all iterations yields total time $O(nm(1 + \rho + \rho^2 + \dots)) = O(nm)$ . When $m = O(k)$ , the overall running time is rectangular $O(kn)$ .
Knowl 4 — Fast Group-Average Agglomerative Clustering via Sum Profiles
algorithm
Group-average agglomerative clustering is a quadratic-time $O(n^2)$ global clustering subroutine that iteratively merges the pair of clusters whose union maximizes the average pairwise similarity among all contained documents. When using normalized document profile vectors $p(\alpha)$ and cosine similarity, the average pairwise similarity $S(\Gamma)$ of a cluster $\Gamma$ is computed directly from its unnormalized sum profile $\tilde{p}(\Gamma) = \sum_{\alpha \in \Gamma} p(\alpha)$ :

$S(\Gamma) = \frac{1}{|\Gamma|(|\Gamma|-1)} \sum_{\alpha \in \Gamma} \sum_{\beta \in \Gamma, \beta \ne \alpha} \langle p(\alpha), p(\beta) \rangle = \frac{\langle \tilde{p}(\Gamma), \tilde{p}(\Gamma) \rangle - |\Gamma|}{|\Gamma|(|\Gamma|-1)}$

For the union $\Lambda = \Gamma \cup \Delta$ of two disjoint clusters $\Gamma$ and $\Delta$ :

$S(\Lambda) = \frac{\langle \tilde{p}(\Lambda), \tilde{p}(\Lambda) \rangle - (|\Gamma| + |\Delta|)}{(|\Gamma| + |\Delta|)(|\Gamma| + |\Delta| - 1)}$

where $\langle \tilde{p}(\Lambda), \tilde{p}(\Lambda) \rangle = \langle \tilde{p}(\Gamma), \tilde{p}(\Gamma) \rangle + 2\langle \tilde{p}(\Gamma), \tilde{p}(\Delta) \rangle + \langle \tilde{p}(\Delta), \tilde{p}(\Delta) \rangle$ .
Input: Set of elements $S$ with $|S| = n_0$ , target cluster count $k$
Output: Partition $\mathcal{G}$ of $S$ into $k$ disjoint clusters
1. Initialize $\mathcal{G} \leftarrow \{\{\alpha\} : \alpha \in S\}$
2. For each singleton cluster $\Gamma = \{\alpha\} \in \mathcal{G}$ :
     Set $\tilde{p}(\Gamma) \leftarrow p(\alpha)$ and $\langle \tilde{p}(\Gamma), \tilde{p}(\Gamma) \rangle \leftarrow 1$
3. For each pair $(\Gamma, \Delta) \in \mathcal{G} \times \mathcal{G}$ with $\Gamma \ne \Delta$ :
     Compute $\langle \tilde{p}(\Gamma), \tilde{p}(\Delta) \rangle$ and calculate candidate merge similarity $S(\Gamma \cup \Delta)$
4. while $|\mathcal{G}| > k$ :
     Find $(\Gamma^*, \Delta^*) = \arg\max_{\Gamma, \Delta \in \mathcal{G}, \Gamma \ne \Delta} S(\Gamma \cup \Delta)$
     Create merged cluster $\Lambda \leftarrow \Gamma^* \cup \Delta^*$
     Compute $\tilde{p}(\Lambda) \leftarrow \tilde{p}(\Gamma^*) + \tilde{p}(\Delta^*)$
     Compute $\langle \tilde{p}(\Lambda), \tilde{p}(\Lambda) \rangle \leftarrow \langle \tilde{p}(\Gamma^*), \tilde{p}(\Gamma^*) \rangle + 2\langle \tilde{p}(\Gamma^*), \tilde{p}(\Delta^*) \rangle + \langle \tilde{p}(\Delta^*), \tilde{p}(\Delta^*) \rangle$
     Update $\mathcal{G} \leftarrow (\mathcal{G} \setminus \{\Gamma^*, \Delta^*\}) \cup \{\Lambda\}$
     For each remaining cluster $\Omega \in \mathcal{G} \setminus \{\Lambda\}$ :
       Compute $\langle \tilde{p}(\Lambda), \tilde{p}(\Omega) \rangle = \langle \tilde{p}(\Gamma^*), \tilde{p}(\Omega) \rangle + \langle \tilde{p}(\Delta^*), \tilde{p}(\Omega) \rangle$
       Update $S(\Lambda \cup \Omega)$
5. return $\mathcal{G}$
Knowl 5 — Document Profile Representation and Cosine Similarity with Square-Root Damping
definition
Let $C$ be a document corpus and $V = \{w_1, w_2, \dots, w_{|V|}\}$ be the vocabulary of unique words in $C$ . Each document $\alpha \in C$ is represented by a countfile vector $c(\alpha) = (f(w_1, \alpha), f(w_2, \alpha), \dots, f(w_{|V|}, \alpha))^T \in \mathbb{R}^{|V|}$ , where $f(w_i, \alpha)$ is the frequency of word $w_i$ in $\alpha$ .

A monotone damping function $g: \mathbb{R} \to \mathbb{R}$ is applied element-wise to the frequencies. The document profile $p(\alpha)$ is defined as the normalized vector:

$p(\alpha) = \frac{g(c(\alpha))}{\|g(c(\alpha))\|}$

Taking $g$ to be the component-wise square-root function $g(x) = \sqrt{x}$ produces empirically superior document clustering results compared to traditional logarithmic damping functions.

The pairwise similarity $s(\alpha, \beta)$ between two documents $\alpha$ and $\beta$ is the cosine of the angle between their damped countfile vectors, which equals the inner product of their unit-length document profiles:

$s(\alpha, \beta) = \langle p(\alpha), p(\beta) \rangle = \sum_{i=1}^{|V|} p(\alpha)_i p(\beta)_i$
Knowl 6 — Trimmed Sum Profile and Cluster Digest
definition
For a document cluster $\Gamma \subseteq C$ , the normalized sum profile $p(\Gamma)$ is defined via the unnormalized sum profile $\tilde{p}(\Gamma)$ :

$\tilde{p}(\Gamma) = \sum_{\alpha \in \Gamma} p(\alpha), \qquad p(\Gamma) = \frac{\tilde{p}(\Gamma)}{\|\tilde{p}(\Gamma)\|}$

To prevent peripheral outlier documents from distorting cluster representations, the trimmed sum profile $p_m(\Gamma)$ is computed over the set $r_m(\Gamma)$ of the $m$ most central documents in $\Gamma$ (those with highest similarity $s(\alpha, \Gamma) = \langle p(\alpha), p(\Gamma) \rangle$ ):

$\tilde{p}_m(\Gamma) = \sum_{\alpha \in r_m(\Gamma)} p(\alpha), \qquad p_m(\Gamma) = \frac{\tilde{p}_m(\Gamma)}{\|\tilde{p}_m(\Gamma)\|}$

where $m$ is either a fixed constant or an adaptive fraction of $|\Gamma|$ . The computation of $r_m(\Gamma)$ runs in $O(|\Gamma|)$ time without requiring a full sort.

The topical words $t_w(\Gamma)$ are defined as the $w$ words in $V$ with the highest weights in $p(\Gamma)$ (or $p_m(\Gamma)$ ).

The $(m, w)$ cluster digest is the pair $(r_m(\Gamma), t_w(\Gamma))$ . It provides a concise summary of cluster $\Gamma$ suitable for display in Scatter/Gather browsing and is computable in $O(|\Gamma| + |V|)$ time.
Knowl 7 — Cluster Partition Refinement Procedures
algorithm
Partition refinement procedures take an initial partition $P = \{\Gamma_1, \dots, \Gamma_k\}$ of corpus $C$ (where $\bigcup_{i=1}^k \Gamma_i = C$ ) and iteratively optimize cluster quality using one or more of three operations:
Input: Partition $P = {\Gamma_1, \dots, \Gamma_k}$ of corpus $C$
Output: Refined partition $P'$
Procedure Iterated Assign-to-Nearest:
  1. For each $\Gamma_i \in P$ , compute trimmed sum profile $p_m(\Gamma_i)$
  2. For each document $\alpha \in C$ , assign $\alpha$ to $\Gamma_i$ that maximizes $s(\alpha, p_m(\Gamma_i))$
  3. Repeat for a small fixed number of iterations (typically 2)
Procedure Split:
  1. For each cluster $\Gamma_i \in P$ , compute self-similarity $A(\Gamma_i) = s(\Gamma_i, \Gamma_i)$
  2. Identify clusters whose rank $r(\Gamma_i, P)$ in sorted self-similarity satisfies $r(\Gamma_i, P) < \rho k$ for a parameter $\rho \in (0, 1]$
  3. For each selected cluster $\Gamma_i$ , apply 2-way Buckshot clustering ( $k=2$ ) to partition $\Gamma_i$ into $\{\Gamma_{i,1}, \Gamma_{i,2}\}$
  4. Replace $\Gamma_i$ in $P$ with $\Gamma_{i,1}$ and $\Gamma_{i,2}$
Procedure Join:
  1. For each cluster $\Gamma_i \in P$ , extract topical words $t_w(\Gamma_i)$
  2. For each pair $(\Gamma_i, \Gamma_j)$ with $i \ne j$ , compute topical word overlap $T(\Gamma_i, \Gamma_j) = |t_w(\Gamma_i) \cap t_w(\Gamma_j)|$
  3. If $T(\Gamma_i, \Gamma_j) > \rho$ for a threshold $\rho \in (0, w]$ , merge $\Gamma_i$ and $\Gamma_j$ into a single cluster
Iterated Assign-to-Nearest runs in $O(kn)$ time. Split runs in $O(n)$ time. Join computes $k^2$ intersections over $w$ -element sets in $O(kn)$ time.
Knowl 8 — Sample Size Bound for Natural Cluster Recovery in Buckshot
theoretical result
Let a document collection $C$ of size $n$ consist of $k$ well-separated, equal-sized natural clusters, defined such that the minimum intra-cluster document similarity is strictly greater than the maximum inter-cluster document similarity.

When Buckshot samples $s$ documents uniformly at random from $C$ , the probability that at least one of the $k$ clusters has zero representatives in the sample is bounded by:

$\mathbb{P}(\text{failure}) \le k \left(1 - \frac{1}{k}\right)^s$

Setting the sample size to $s = a k \ln k$ for a constant $a > 0$ yields:

$\mathbb{P}(\text{failure}) \le k \left(1 - \frac{1}{k}\right)^{a k \ln k} < k^{1-a}$

Consequently, as long as $n \gg k \ln k$ , choosing $s = \sqrt{kn}$ satisfies $s \ge a k \ln k$ for moderate $k$ . For $k = 20$ clusters, choosing $a = 5$ requires $s = 400$ samples, which guarantees that all $k$ cluster seeds are sampled with probability greater than $0.999$ ( $999$ times out of $1000$ ). When every natural cluster contains at least one sampled seed, the resulting clusters produced by the agglomerative subroutine are pure subsets of the true clusters.
Knowl 9 — Interactive Latency and Topic Discovery on the New York Times Corpus
empirical result
Scatter/Gather was evaluated on an experimental corpus of approximately 5,000 articles (~30 megabytes of ASCII text) published by the New York Times News Service during August 1990.

The system achieved interactive response times across sequential scatter-gather steps using Buckshot followed by 2 iterations of Assign-to-Nearest refinement:
1. Initial scatter ( $n = 4,970$ articles, $k = 8$ clusters): Sampled 199 items for seed agglomeration; Assign-to-Nearest converged across iterations to sizes $(287, 1731, 749, 275, 481, 844, 310, 293)$ in 131,258 ms (~131 s).
2. Second scatter ( $n = 1,903$ gathered articles from Iraq, Oil, and Germany clusters, $k = 8$ ): Sampled 123 items; converged to sizes $(650, 66, 57, 117, 59, 242, 586, 126)$ in 54,184 ms (~54 s), separating Iraq into military deployment, oil market effects, and Kuwait hostages.
3. Third scatter ( $n = 176$ gathered articles from Pakistan and African issues clusters, $k = 8$ ): Sampled 37 items; converged to cluster sizes $(5, 16, 28, 1, 51, 7, 55, 13)$ in 11,140 ms (~11 s).
The multi-step browsing process uncovered low-frequency international stories (such as a coup in Pakistan, hostage taking in Trinidad, and the civil war in Liberia) that were completely submerged in global corpus queries.

Coverage note — None. All substantial contributions from the paper—including the Scatter/Gather paradigm, Buckshot, Fractionation, group-average agglomerative clustering with sum profiles, profile representations, cluster digests, refinement operators, sample bounds, and empirical evaluation—have been captured as knowls.

References

1.Chris Buckley and Alan F. Lewit. Optimizations of inverted vector searches. In Proceedings of the Eighth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 97–110, 1985.
2.W.B. Croft. Clustering large files of documents using the single-link method. Journal of the American Society for Information Science, 28:341–344, 1977.
3.A. El-Hamdouchi and P. Willett. Hierarchical document clustering using Ward’s method. In Proceedings of the Ninth International Conference on Research and Development in Information Retrieval, pages 149–156, 1986.
4.A. Griffiths, H.C. Luckhurst, and P. Willett. Using inter-document similarity information in document retrieval systems. Journal of the American Society for Information Science, 37:3–11, 1986.
5.Anil K. Jain and Richard C. Dubes. Algorithms for Clustering Data. Pretice Hall, Engelwood Cliffs, N.J. 07632, 1988.
6.N. Jardine and C.J. van Rijsbergen. The use of hierarchical clustering in information retrieval. Information Storage and Retrieval, 7:217–240, 1971.
7.J. O. Pedersen, D. R. Cutting, and J. W. Tukey. Snippet search: a single phrase approach to text access. In Proceedings of the 1991 Joint Statistical Meetings. American Statistical Association, 1991. Also available as Xerox PARC technical report SSL-91-08.
8.G. Salton. The SMART Retrieval System. Prentice-Hall, Englewood Cliffs, N.J., 1971.
9.G. Salton and M. J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.
10.R. Sibson. SLINK: an optimally efficient algorithm for the single link cluster method. Computer Journal, 16:30–34, 1973.
11.C.J. van Rijsbergen. Information Retrieval. Butterworths, London, second edition, 1979.
12.C.J. van Rijsbergen and W.B. Croft. Document clustering: An evaluation of some experiments with the Cranfield 1400 collection. Information Processing & Management, 11:171–182, 1975.
13.P. Willett. Document clustering using an inverted file approach. Journal of Information Science, 2:223–231, 1980.
14.P. Willett. A fast procedure for the calculation of similarity coefficients in automatic classification. Information Processing & Management, 17:53–60, 1981.
15.P. Willett. Recent trends in hierarchical document clustering: A critical review. Information Processing & Management, 24(5):577–597, 1988.

Citation

MLA

Cutting, D. R., et al. “Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections”. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval - SIGIR '92, 1992, pp. 318–29, https://doi.org/10.1145/133160.133214.

APA

Cutting, D. R., Karger, D. R., Pedersen, J. O., & Tukey, J. W. (1992). Scatter/Gather: a cluster-based approach to browsing large document collections. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval - SIGIR '92, 318–329. https://doi.org/10.1145/133160.133214

Chicago

Cutting, D. R., D. R. Karger, J. O. Pedersen, and J. W. Tukey. 1992. “Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections”. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval - SIGIR '92, 318–29. https://doi.org/10.1145/133160.133214.

Harvard

Cutting, D.R. et al. (1992) “Scatter/Gather: a cluster-based approach to browsing large document collections”, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '92. ACM Press, pp. 318–329. Available at: https://doi.org/10.1145/133160.133214.

Vancouver

1. Cutting DR, Karger DR, Pedersen JO, Tukey JW (1992) Scatter/Gather: a cluster-based approach to browsing large document collections. In: Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '92. ACM Press, pp 318–329

BibTeX

@inproceedings{Cutting_1992, series={SIGIR ’92}, title={Scatter/Gather: a cluster-based approach to browsing large document collections}, url={http://dx.doi.org/10.1145/133160.133214}, DOI={10.1145/133160.133214}, booktitle={Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval  - SIGIR ’92}, publisher={ACM Press}, author={Cutting, Douglass R. and Karger, David R. and Pedersen, Jan O. and Tukey, John W.}, year={1992}, pages={318–329}, collection={SIGIR ’92} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Scatter/Gather: a cluster-based approach to browsing large document collections

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Scatter/Gather Document Browsing Paradigm

Knowl 2 — Buckshot Fast Partitional Clustering Algorithm

Knowl 3 — Fractionation Linear-Time Clustering Algorithm

Knowl 4 — Fast Group-Average Agglomerative Clustering via Sum Profiles

Knowl 5 — Document Profile Representation and Cosine Similarity with Square-Root Damping

Knowl 6 — Trimmed Sum Profile and Cluster Digest

Knowl 7 — Cluster Partition Refinement Procedures

Knowl 8 — Sample Size Bound for Natural Cluster Recovery in Buckshot

Knowl 9 — Interactive Latency and Topic Discovery on the New York Times Corpus

References

Citation

BibTeX

Access the Paper