  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.
