DynamicDiscreteSamplersComparisons

Performance and exactness comparisons between different implementations of Dynamic Discrete Samplers.

Currently, it compares four algorithms:

• EBUS (https://github.com/LilithHafner/WeightVectors.jl)
• BUS (https://github.com/CUHK-DBGroup/WSS-WIRS)
• FT (https://github.com/manpen/dynamic-weighted-index)
• DPA* (https://github.com/Daniel-Allendorf/proposal-array)

Four performance benchmarks and one exactness benchmark are performed:

• performance test on static sampling
• performance test on dynamic sampling with a fixed domain
• performance test on dynamic sampling with an increasing domain
• performance test on dynamic sampling with a decreasing domain
• exactness test by an exponential decay strategy

For more information, refer to the paper listed in the citation section.

Execution

To run the benchmarks on Linux, first install the necessary softwares with

bash install.sh

and then run the benchmarks with

bash run.sh

Results

The results are stored in csv format in the data folder, and as plots in the figures folder:

Citation

If you use this package in a publication, or simply want to refer to it, please cite the paper below:

@misc{hafner2025exactsampler,
      title={Exact and Efficient Sampling from Dynamic Discrete Distributions with Finite-Precision Weights}, 
      author={Lilith Orion Hafner and Adriano Meligrana},
      year={2025},
      eprint={2506.14062},
      archivePrefix={arXiv},
      primaryClass={cs.DS},
      url={https://arxiv.org/abs/2506.14062}, 
}

This comparison accompanies the EBUS implementation available at https://github.com/LilithHafner/WeightVectors.jl.