Sum and moment estimation improved by weighted sampling techniques
Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling
Data Structures and Algorithms
Summary
The problem is how to estimate the total sum or the moments (a type of average measure) of data efficiently by looking at only part of it. The authors designed a new way to take samples with different weights that nearly matches the best possible performance for each specific data instance. They also proved a matching limitation, showing their approach is close to the best you can do. Additionally, they developed a new method for estimating moments that uses fewer samples depending on the data.
What this means in practice
- •For data engineers: Design sampling strategies that minimize the number of data points needed to estimate totals in datasets with varying importance or frequency.
- •For data analytics teams: Improve moment calculations for large-scale datasets where exact computations are costly but estimations with fewer samples are needed.
Authors
Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan
Abstract
We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to the $\ell_2$ norm of the weighted sampling distribution. We show an almost instance optimal lower bound for this problem as well. We also study the moment estimation problem and design an algorithm that has better instance-wise sample complexity bounds.