CAMP: Coreset Accelerated Metacell Partitioning enables scalable analysis of single-cell data

Abstract

Scaling metacell inference to atlas-level single-cell datasets demands algorithms that are both computationally efficient and geometrically faithful. We introduce CAMP (Coreset Accelerated Metacell Partitioning), a metacell framework that preserves the intrinsic structure of the cellular manifold while enabling scalable analysis of millions of cells. CAMP leverages coreset-based sampling to construct a small, weighted subset of representative cells that approximates the full dataset with provable geometric guarantees. This formulation transforms metacell construction into a coreset inference problem, reducing runtime and memory complexity by up to an order of magnitude without loss of accuracy. Through extensive experiments, we show that CAMP produces metacells that are compact, well-separated, and biologically coherent, achieving performance on par with or exceeding existing methods including MetaCell, SuperCell, SEACells, and MetaQ. By combining theoretical efficiency with empirical robustness, CAMP establishes coreset acceleration as a principled foundation for scalable, high-fidelity metacell inference in single-cell transcriptomics.