A Divide-and-Merge Methodology for Clustering

Full textClick to download.
CitationIn Proc. of 24th ACM Symposium on Principles of Database Systems (PODS), 2005.
AuthorsDavid Cheng
Ravi Kannan
Santosh Vempala
Grant Wang


We present a divide-and-merge methodology for clustering a set of objects that combines a top-down ``divide'' phase with a bottom-up ``merge'' phase. We use an efficient spectral algorithm for the divide phase and a simple strategy for the merge phase. We present a meta-search engine that uses this technology to cluster results from web searches. We also give emperical results on text-based data where the algorithm performs better than or competitively with well-used existing methods.

Back to publications
Back to previous page