Mixture of Sketches: Learning-Augmented Distributed Sketch Aggregation with NetSketch

Estimating frequencies of elements in a distributed data stream is a key task in machine learning, databases, and network measurement. It utilizes popular sketches such as count-min sketch (CMS) to collect data with worst-case error guarantees in the single-node setting, while a global frequency view is obtained by maintaining per-node sketches and aggregating them counter-wise. State-of-the-art sketches attach learned neural corrections to sketches to mitigate single-node errors, but per-node correction easily ignores cross-node statistics after aggregation. To address this problem, we propose NetSketch, an implementation of mixture of sketches (MoS) with a local correction module (LCM) at each node and a merge-aware correction module (MACM) at the aggregator. Each node runs the LCM and transfers its corrected sketch and compact summary while the aggregator counter-wise merges the corrected sketches and runs the MACM with cross-node statistics to produce global estimates. Extensive experiments on eight real-world workloads show that NetSketch achieves 1.6$\times$-17.2$\times$ AAE reduction over six state-of-the-art baselines. Our analysis further characterizes why the two-level design helps, i.e., it improves the aggregation-error dependence from $\Omega (K{ϵ}_{\mathrm{single}})$ for single-level correction to $O(\sqrt{K}{ϵ}_{\mathrm{single}})$ for MoS, with a finite-sample refinement and a matching lower bound.