A Divide-and-Merge Methodology for Clustering

Summary: Divide-and-merge clustering: spectral top-down divide builds a tree of items; bottom-up merge efficiently finds optimal tree-respecting partitions for many objectives (k-means, min-diameter, min-sum, correlation). Applied to web meta-search and text data, competitive or superior to prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1352
Venue: PODS
Year: 2005
Pagerank: -
Overall Rank: 13,845 | 5.02%
DOI: 10.1145/1065167.1065192

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. David Cheng (Massachusetts Institute of Technology)
2. Ravi Kannan (Yale University)
3. Santosh Vempala (Massachusetts Institute of Technology)
4. Grant Wang (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{cheng_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{A Divide-and-Merge Methodology for Clustering}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065192},
        doi = {10.1145/1065167.1065192},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cheng, David and Kannan, Ravi and Vempala, Santosh and Wang, Grant},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,161	Efficient Algorithm for K-Multiple-Means	2024	SIGMOD
2	4,812	Clustering by Pattern Similarity in Large Data Sets	2002	SIGMOD
3	364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB
4	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
5	14,127	Clustering Methods for Large Databases: From the Past to the Future	1999	SIGMOD
6	12,053	K-means Split Revisited: Well-grounded Approach and Experimental Evaluation	2016	SIGMOD
7	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
8	8,778	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB
9	12,816	Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces	2003	VLDB
10	11,253	Ensemble Clustering based on Meta-Learning and Hyperparameter Optimization	2024	VLDB