A Scalable Parallel Algorithm for Balanced Sampling (Student Abstract)

Alexander W. Lee, Stefan Walzer-Goldfeld, Shukry Zablah, Matteo RiondatoAAAI 2022 · DOI

Introduction

Balanced sampling is a critical statistical technique used to ensure that a sample accurately represents a larger population by matching known auxiliary data. While the "cube method" is the gold standard for achieving this balance, its inherently sequential nature makes it computationally prohibitive for massive datasets. As populations scale into the millions or billions, traditional methods become a bottleneck in modern data analytics. This research presents a novel parallel algorithm that overcomes these limitations by adapting the cube method using "fake strata" to distribute the workload across multiple processors.

Methodology: The Parallel Cube Method

The proposed approach leverages the concept of the stratified cube method, typically used for populations with natural groupings. By treating arbitrary partitions of the data as "fake strata," the algorithm enables efficient parallelization:

  1. Fake Strata Partitioning: The population is split into $p$ arbitrary strata, where $p$ corresponds to the number of available processors.
  2. Parallel Flight Phase: Each processor independently executes a "flight phase"—a random walk on the constraint space—for its assigned stratum. This step reduces dimensionality locally and occurs simultaneously across all cores.
  3. Global Merge and Landing: The results from all processors are concatenated for a final global flight phase and a "landing phase." This concluding step resolves any remaining non-integral values to produce the final sample.

Experimental Setup

The algorithm's scalability was evaluated using artificial datasets designed to simulate high-dimensional sampling challenges. Population sizes ($N$) ranged from 2,500 to $10^7$ units, with 10 auxiliary variables per unit. Inclusion probabilities and auxiliary variables were drawn from a uniform distribution $[0, 1)$. The Python-based implementation was benchmarked against established sequential R packages, such as cubesampling and BalancedSampling.

Results and Discussion

The parallel algorithm successfully preserved the balancing quality of the original cube method, maintaining an absolute relative deviation from population totals of less than 0.5%.

The primary advantage of this approach is its scalability. For large populations ($N \ge 10^5$), the time spent in the parallel flight phase dominates the total execution time, leading to near-ideal linear speedup. On a 32-vCPU machine, doubling the number of processors roughly halved the runtime for a population of 10 million.

Runtime performance across different population sizes ($N$) and processor counts ($p$), illustrating the transition from overhead-dominated small scales to near-ideal speedup at large scales.

However, parallelization introduces overhead in the form of setup and merging costs. As shown in the figure above, for small populations (e.g., $N = 2500$), the "end" phase (merging and rounding) and setup costs can make the parallel version slower than sequential execution. The "aha moment" occurs at $N = 10^7$, where the parallel processing time significantly outweighs these fixed costs.

Conclusion and Future Work

While highly effective for large-scale data, the algorithm is less efficient for small datasets due to the relative weight of management overhead. Additionally, increasing the number of strata complicates the final rounding phase, suggesting a potential upper bound on the number of processors relative to population size. Future research will focus on applying this scalable sampling technique to real-world downstream analytics tasks to quantify improvements in model estimation accuracy and efficiency.

Summary updated

BibTeX
@inproceedings{lee2022scalable,
  author = {Alexander W. Lee and Stefan Walzer-Goldfeld and Shukry Zablah and Matteo Riondato},
  title = {{A Scalable Parallel Algorithm for Balanced Sampling (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21632},
}
Figure