Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially

Summary: Coreset-based 2-round MapReduce for k-center with/without outliers; 1-pass streaming for the outlier variant. Achieves epsilon-additive approximation to best sequential k-center; space-efficient for small doubling dimension, empirical scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12191
Venue: VLDB
Year: 2019
Pagerank: 6.7407122e-05
Overall Rank: 4,366 | 70.05%
DOI: 10.14778/3317315.3317319

Incoming Non-self Citations Over Time

Authors

1. Matteo Ceccarello (Basic Algorithms Research Copenhagen; IT University of Copenhagen)
2. Andrea Pietracaprina (University of Padova)
3. Geppino Pucci (University of Padova)

BibTeX Citation

@article{ceccarello_vldb19,
        title = {{Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially}},
        author = {Ceccarello, Matteo and Pietracaprina, Andrea and Pucci, Geppino},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {7},
        pages = {766--778},
        doi = {10.14778/3317315.3317319},
        url = {https://doi.org/10.14778/3317315.3317319},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	5.4938502e-05
9,075	LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets	2020	VLDB	5.3251649e-05
10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	5.093636e-05
11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS	5.093636e-05
11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
2,959	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	7.9182968e-05
5,847	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	6.0676282e-05
6,345	Clustering Uncertain Graphs	2018	VLDB	5.9059861e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,795	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD
2	3,958	Continuous Outlier Detection in Data Streams: An Extensible Framework and State-Of-The-Art Algorithms	2013	SIGMOD
3	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
4	693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB
5	11,184	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD
6	9,575	Local Search Methods for k-Means with Outliers	2017	VLDB
7	5,847	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB
8	10,065	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD
9	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD
10	10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS