Research map / Learning theory and algorithms / Clustering

Fully-Scalable Massively Parallel Algorithm for k-center with Outliers

AAAI 2025 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes the first fully-scalable (sublinear local space) MPC algorithm for the (k,z)-center problem with outliers, using iterative sampling with adaptive sample sizes and weight truncation.

Problem

Existing MPC algorithms for the k-center problem with outliers need Ω(k) local space per machine, which is impractical for large k; the paper targets sublinear-local-space (fully-scalable) MPC algorithms with bounded approximation and outlier loss.

Approach

An outliers-removal sampling (ORS) procedure based on LSH block partitioning and random ball covering, iterated over O(log log n) rounds with an (ε,η)-self-adaptive sample size and a τ-weight truncation to bound discarded inliers and opened outlier centers.

Key results

• Gives an O(log* n)-approximation MPC algorithm for (k,z)-center in constant-dimensional Euclidean space, discarding at most (1+ε)z outliers.
• Runs in O(log log n) rounds with local space Θ(n^δ) per machine and total space Õ(n^{1+δ} log^2 Δ).
• Uses k(1+o(1)) + k·Õ(log n)/ε opened centers.

Limitations

• Assumes each outlier is at least Õ(4c_ρ r*) away from every inlier.
• Requires z ≥ k·Õ(log n)/ε outliers and bounded aspect ratio for the total-space bound.
• Only for constant-dimensional Euclidean space; the full proofs are deferred to an unavailable full version.

Experimental setup

Metrics: approximation ratio number of discarded outliers number of MPC rounds local space per machine

Baselines: Malkomes et al. 2015 Ceccarello et al. 2019 de Berg et al. 2023 Bateni et al. 2021 Coy, Czumaj, and Mishra 2023

Builds on: Charikar et al. 2001 (k-center with outliers) Coy, Czumaj, and Mishra 2023 (O(log* n) fully-scalable k-center) Bateni et al. 2021 (fully-scalable MPC k-center) Har-Peled, Indyk, Motwani LSH

Closest papers by meaning

• Fast Algorithms for Distributed k-Clustering with Outliers (ICML 2023 · similarity 0.90)
• Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.88)
• Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.87)
• Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.85)
• Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.85)