Web document clustering: a feasibility demonstration
Oren ZamirOren Etzioni
Introduces Suffix Tree Clustering, a linear-time algorithm that groups web search results into overlapping, phrase-labeled clusters using only search engine snippets rather than full document texts.
Web search engines typically present results as long, ranked lists of document summaries. Because search engines suffer from low precision and users face extensive result sets, finding relevant information by sifting through these linear lists is inefficient and time-consuming. Grouping search results into topical clusters offers an alternative browsing method, but traditional clustering techniques are generally too slow for real-time web use and fail to address the specific constraints of web search results.
The article evaluates whether post-retrieval document clustering is feasible for web search results and introduces a novel algorithm called Suffix Tree Clustering to meet the performance and usability demands of the web.
To evaluate this approach, the authors developed a prototype meta-search system and gathered 10 distinct web document collections, each containing 200 search snippets and their full web pages, across defined search queries with manually assigned relevance ratings. The analysis benchmarked Suffix Tree Clustering against standard algorithms—including hierarchical and iterative techniques—across retrieval precision, processing speed, and the impact of clustering short snippets versus full document texts.
The findings demonstrate four major outcomes. First, Suffix Tree Clustering outperformed traditional clustering algorithms and the default ranked list, achieving the highest average precision. Second, clustering short snippets (averaging about 20 informative words) resulted in only a slight reduction in cluster quality compared to clustering full web pages (averaging 220 informative words). Third, the algorithm operates in linear time relative to collection size and processes documents incrementally as they arrive over the network, returning clustered results in roughly 0.01 seconds after the final document download. Finally, allowing documents to belong to multiple clusters and identifying multi-word phrases were both critical to performance; 72% of documents were placed in multiple clusters, and 55% of the base clusters relied on multi-word phrases.
These results indicate that search engines and meta-search services do not need to download entire web pages or invest heavy server resources to group results meaningfully. By operating incrementally on snippet text alone, clustering can be deployed on separate intermediary machines without creating perceptible latency for users. Furthermore, extracting shared multi-word phrases naturally generates informative, browsable labels for each cluster.
Organizations developing search and information retrieval interfaces should consider deploying incremental phrase-based clustering on snippets rather than relying solely on ranked lists or computationally expensive full-text clustering. Future implementation should include controlled user studies to measure how human searchers interact with cluster labels and navigate overlapping categories in practice.
The conclusions are subject to certain limitations. The evaluation relied on a relatively small test set of 10 queries and assumed an idealized user who consistently identifies and selects the most relevant cluster. While technical performance and speed metrics are robust, direct validation of user productivity and satisfaction in live environments remains necessary.
- Paper: Scatter/Gather: a cluster-based approach to browsing large document collections, Douglass R. Cutting et al. (1992). Introduces Scatter/Gather, the foundational cluster-based browsing paradigm for information retrieval that the source adapts and improves for web search snippets.
- Paper: BIRCH: an efficient data clustering method for very large databases, Tian Zhang et al. (1996). Establishes linear-time incremental clustering fundamentals for large-scale datasets, informing the scalability goals addressed by Suffix Tree Clustering.
- Paper: Indexing By Latent Semantic Analysis, Scott Deerwester et al. (1990). Provides the foundational vector-space and latent semantic models for document representation against which phrase-based snippet clustering is contrasted.
- Paper: Knowledge Acquisition Via Incremental Conceptual Clustering, DOUGLAS H. FISHER (1987). Presents early incremental conceptual clustering techniques that motivate the design of linear-time, dynamic grouping methods for incoming text streams.
- Paper: Web mining research: a survey, Raymond Kosala et al. (2000). Surveys the broader taxonomy of web mining research, contextualizing web document and snippet clustering within search and text discovery architectures.
- Paper: Co-clustering documents and words using bipartite spectral graph partitioning, Inderjit S. Dhillon (2001). Extends text collection partitioning by simultaneously clustering words and documents via bipartite spectral graph partitioning to capture phrase-document interactions.
- Paper: Document clustering based on non-negative matrix factorization, Wei Xu et al. (2003). Advances document clustering and topic discovery by using non-negative matrix factorization to generate interpretable topic representations from text collections.
- Paper: Web-scale k-means clustering, D. Sculley (2010). Applies modern optimization techniques such as mini-batch k-means to achieve the ultra-low latency required for web-scale search result clustering.
- Paper: Concept Decompositions for Large Sparse Text Data Using Clustering, I. Dhillon et al. (2004). Develops spherical concept decomposition methods to handle the high dimensionality and sparsity inherent in large-scale text clustering.
- Paper: The use of MMR, diversity-based reranking for reordering documents and producing summaries, Jaime Carbonell et al. (1998). Explores maximal marginal relevance as an alternative post-retrieval reranking and summarization technique to reduce redundancy in search result lists.
