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.

Two Technical Lectures

I try to watch a technical lecture or two every weekend, this week I actually stumbled upon two good lectures.

http://videolectures.net/is04_munro_sds/

About succinct data structure, … how to index stuff without using much memory, … in other words, … compressing trees.

http://videolectures.net/solomon_langford_fenna/

Spatial data structures for fast and exact nearest neighbor queries, in high dimensional spaces. I was originally interested in special data structures men ayam el physics engine wel collision detection in games, but they can also be used to speed-up some data clustering algorithms.