Optimal data structures for stochastic driven simulations

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

Research output: Contribution to journalArticleAcademic

29 Downloads (Pure)

Abstract

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
JournalarXiv
Publication statusPublished - 7 Feb 2018

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

Cite this