Abstract
Random sampling is an essential tool in the processing and transmission of data. It is used to summarize data too large to store or manipulate and meet resource constraints on bandwidth or battery power. Estimators that are applied to the sample facilitate fast approximate processing of queries posed over the original data and the value of the sample hinges on the quality of these estimators. Our work targets data sets such as request and traffic logs and sensor measurements, where data is repeatedly collected over multiple instances: time periods, locations, or snapshots. We are interested in queries that span multiple instances, such as distinct counts and distance measures over selected records. These queries are used for applications ranging from planning to anomaly and change detection. Unbiased low-variance estimators are particularly effective as the relative error decreases with the number of selected record keys. The Horvitz-Thompson estimator, known to minimize variance for sampling with "all or nothing" outcomes (which reveals exact values or no information on estimated quantity), is not optimal for multi-instance operations for which an outcome may provide partial information. We present a general principled methodology for the derivation of (Pareto) optimal unbiased estimators over sampled instances and aim to understand its potential. We demonstrate significant improvement in estimate accuracy of fundamental queries for common sampling schemes.
Introduction
In the era of big data, random sampling is a cornerstone for managing massive datasets, enabling efficient processing and storage. Traditionally, the Horvitz-Thompson (HT) estimator has been the standard for unbiased estimation. However, HT operates on an "all-or-nothing" principle: it assumes that if a data point is not sampled, no information is gained about its value.
This paper identifies a significant inefficiency in HT when dealing with multi-instance data—such as traffic logs collected over different time intervals or sensor readings from various locations. The key insight is that even when a record is not sampled, the sampling process itself reveals "partial information." For instance, knowing a value was not sampled implies it fell below a specific threshold. By exploiting this information, the authors derive estimators that significantly outperform HT in multi-instance queries like maximums, minimums, and distinct counts.
Methodology
The authors propose a principled methodology for deriving Pareto optimal unbiased estimators. An estimator is considered Pareto optimal if its variance cannot be reduced for one data vector without increasing it for another. The framework introduces "Order-based Optimality," where an algorithm ($\hat{f}^{(\prec)}$) minimizes variance based on a predefined order of possible data vectors.
A critical factor in this framework is the use of "known seeds." By using reproducible hash functions for sampling, the estimator can determine the exact sampling thresholds used for each instance, even if a record wasn't selected. This allows for tighter bounds on unsampled values. The authors derive specific families of estimators, such as $\hat{max}^{(L)}$ (optimized for "dense" data with similar values across instances) and $\hat{max}^{(U)}$ (optimized for "sparse" data).
The table above illustrates the result of this methodology for the $\hat{max}^{(L)}$ estimator across two instances. It shows how the estimate is calculated for every possible sampling outcome $S$, incorporating the sampling probabilities $p_1, p_2$ and the observed values $v_1, v_2$. This approach moves away from ad-hoc estimator design toward a mathematically rigorous derivation of optimality.
Results
The researchers evaluated their estimators using both synthetic datasets and real-world IP traffic logs. The results were striking:
- Variance Reduction: For Boolean OR queries, which are essential for distinct counting, the new estimators reduced variance by a factor of two to four compared to the standard HT estimator.
- Real-World Performance: On IP traffic logs containing approximately $2.45 \times 10^4$ distinct destination IPs, the $\hat{max}^{(L)}$ estimator achieved a variance reduction ratio between 2.45 and 2.7 over HT when estimating the "Max Dominance" norm.
- Theoretical Robustness: The work successfully characterized the joint sample distributions for dispersed instances, providing a framework that leverages the value of "nothing" (unsampled records) to improve overall accuracy.
Conclusion and Future Work
This research demonstrates that significant gains in estimation accuracy are possible by moving beyond the "all-or-nothing" paradigm of traditional sampling. While the manual derivation of these optimal estimators can be complex, the potential for variance reduction in big data applications is substantial.
Future work will focus on automating the derivation process, potentially creating tools that take a sampling scheme and a query function as input to automatically generate optimal estimator code. Additionally, extending these techniques to a broader range of non-linear multi-instance functions remains an active area for exploration.
Summary updated