Suffix Tree Clustering

I recently stumbled upon this very interesting paper:

Web Document Clustering: A Feasibility Demonstration , by Zamir and Etzioni. PDF here

The paper presents an attractive technique for clustering documents using Suffix Trees, the merits of which can be summarized as:

• The algorithm is incremental, meaning that documents can be added at any time and clusters can be re-evaluated accordingly
• Does this in linear complexity O(n)
Deals with documents as strings, not as Bags of Words, which allows for accounting for context
• The algorithm actually produces sequences of words that represent each cluster (with no extra cost)
Can produce clusters that are not mutually exclusive (fuzzy clusters)
and finally the authors claim it can work efficiently on search engine snippets

Suffix Trees are data structures that are very suitable for indexing text documents (for search purposes), and I think it very devious to exploit the same structure for clustering.