Optimal data structures for stochastic driven simulations

F. D'Ambrosio, G.T. Barkema, H.L. Bodlaender

Research output: Contribution to journalArticleAcademic

39 Downloads (Pure)


Simulations where we have some prior information on the probability distribution of possible outcomes are common in many fields of science (physics, chemistry, biochemistry, etc). Optimal data structures that allow dynamic updates without regenerating the whole structure are crucial for both efficient and accurate results, especially at large scale. In this paper, we describe three different methods: the Binary Tree, the Rejection algorithm and the Composition-Rejection algorithm. We analyze the expected time to extract and update an outcome, for each of the studied methods, for different distributions of the rates of outcomes. We give both a theoretical analysis, and an experimental verification in a real-life setting, and show for different settings which methods give the best expected times.
Original languageEnglish
Article number1802.02379
Number of pages16
Publication statusPublished - 7 Feb 2018


Dive into the research topics of 'Optimal data structures for stochastic driven simulations'. Together they form a unique fingerprint.

Cite this