Data Bubbles: Quality Preserving Performance Boosting for Hierarchical Clustering

Summary: Introduces Data Bubbles, a compression-based pipeline to scale OPTICS: compress to representatives, cluster the compressed data, then infer the full clustering. Tackles three failure modes of naive sampling/BIRCH via post-processing and the Data Bubble concept, enabling near-accurate clustering at high compression with minimal quality loss. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3321
Venue: SIGMOD
Year: 2001
Pagerank: 5.3321448e-05
Overall Rank: 9,013 | 38.17%
DOI: 10.1145/375663.375672

Incoming Non-self Citations Over Time

Authors

1. Markus M. Breunig (University of Munich)
2. Hans-Peter Kriegel (University of Munich)
3. Peer Kröger (University of Munich)
4. Jörg Sander (University of British Columbia)

BibTeX Citation

@inproceedings{breunig_sigmod01,
        title = {{Data Bubbles: Quality Preserving Performance Boosting for Hierarchical Clustering}},
        author = {Breunig, Markus M. and Kriegel, Hans-Peter and Kröger, Peer and Sander, Jörg},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375672},
        url = {https://dl.acm.org/doi/10.1145/375663.375672},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,023	C2P: Clustering based on Closest Pairs	2001	VLDB	5.7242118e-05
7,291	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD	5.6539603e-05
12,816	Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces	2003	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
291	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00022264197

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,949	A New Compression Method with Fast Searching on Large Databases	1987	VLDB
2	11,647	Data Summarization with Hierarchical Taxonomy	2021	SIGMOD
3	907	A Framework for Clustering Evolving Data Streams	2003	VLDB
4	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
5	5,867	Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space	2018	SIGMOD
6	5,963	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD
7	11,274	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB
8	31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD
9	12,816	Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces	2003	VLDB
10	7,291	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD