A Biased Estimator for MinMax Sampling and Distributed Aggregation
This work addresses data reduction for distributed systems with network constraints, offering an incremental improvement over existing unbiased methods.
The paper tackles the problem of reducing data transmission over constrained networks by proposing B-MinMax, a biased estimator for MinMax sampling that trades bias for lower variance, resulting in strictly lower MSE in non-aggregated cases and improved performance in aggregated settings with small sample sizes.
MinMax sampling is a technique for downsampling a real-valued vector which minimizes the maximum variance over all vector components. This approach is useful for reducing the amount of data that must be sent over a constrained network link (e.g. in the wide-area). MinMax can provide unbiased estimates of the vector elements, along with unbiased estimates of aggregates when vectors are combined from multiple locations. In this work, we propose a biased MinMax estimation scheme, B-MinMax, which trades an increase in estimator bias for a reduction in variance. We prove that when no aggregation is performed, B-MinMax obtains a strictly lower MSE compared to the unbiased MinMax estimator. When aggregation is required, B-MinMax is preferable when sample sizes are small or the number of aggregated vectors is limited. Our experiments show that this approach can substantially reduce the MSE for MinMax sampling in many practical settings.