WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement
This work addresses a fundamental issue in data analysis and machine learning pipelines for efficient estimation and sparse representations, particularly in scenarios with skewed data distributions.
The paper tackled the problem of weighted sampling without replacement for skewed weight distributions, introducing novel composable sketches for $\ell_p$ sampling with $p\in[0,2]$ that have linear size growth and are the first to handle $p>1$ and signed updates for $p>0$.
Weighted sampling is a fundamental tool in data analysis and machine learning pipelines. Samples are used for efficient estimation of statistics or as sparse representations of the data. When weight distributions are skewed, as is often the case in practice, without-replacement (WOR) sampling is much more effective than with-replacement (WR) sampling: it provides a broader representation and higher accuracy for the same number of samples. We design novel composable sketches for WOR $\ell_p$ sampling, weighted sampling of keys according to a power $p\in[0,2]$ of their frequency (or for signed data, sum of updates). Our sketches have size that grows only linearly with the sample size. Our design is simple and practical, despite intricate analysis, and based on off-the-shelf use of widely implemented heavy hitters sketches such as CountSketch. Our method is the first to provide WOR sampling in the important regime of $p>1$ and the first to handle signed updates for $p>0$.