<abstract xmlns="http://www.w3.org/1999/xhtml"><p> Since the last two decades huge systems (such as giant graphs, big data structures, . . . ) have played a central role in computer science, and with the technology improvements, those large objects are now massively used in practice. In order to handle them we need to analyse some typical properties of models of large objects. One way to study typical behaviours consists in generating random objects to get some experimental results on their properties. A new technique has been introduced ten years ago: the Boltzmann sampling. It has been presented by Duchon et al, and is based on automatic interpretation in terms of samplers of the specification of the combinatorial objects under study.</p><p>One of the core problem in Boltzmann sampling lies in the distribution of the object sizes, and the choice of some parameters in order to get the more appropriate size distribution. From this choice depends the efficiency of the sampling. Moreover some additional ideas allows to improve the efficiency, one of them is based on some anticipated rejections, the other one on the combinatorial differentiation of the specification. Anticipated rejection consists during the recursive building of a random object to kill the process as soon as we are sure to exceed the maximum target size, rather than waiting until the natural end of the process. In the original paper, while both approaches have been presented, and used on the same kind of structures, the methods are not compared. We propose in this paper a detailed comparison of both approaches, in order to understand precisely which method is the more efficient. </p></abstract>

Since the last two decades huge systems (such as giant graphs, big data structures, . . . ) have played a central role in computer science, and with the technology improvements, those large objects are now massively used in practice. In order to handle them we need to analyse some typical properties of models of large objects. One way to study typical behaviours consists in generating random objects to get some experimental results on their properties. A new technique has been introduced ten years ago: the Boltzmann sampling. It has been presented by Duchon et al, and is based on automatic interpretation in terms of samplers of the specification of the combinatorial objects under study.One of the core problem in Boltzmann sampling lies in the distribution of the object sizes, and the choice of some parameters in order to get the more appropriate size distribution. From this choice depends the efficiency of the sampling. Moreover some additional ideas allows to improve the efficiency, one of them is based on some anticipated rejections, the other one on the combinatorial differentiation of the specification. Anticipated rejection consists during the recursive building of a random object to kill the process as soon as we are sure to exceed the maximum target size, rather than waiting until the natural end of the process. In the original paper, while both approaches have been presented, and used on the same kind of structures, the methods are not compared. We propose in this paper a detailed comparison of both approaches, in order to understand precisely which method is the more efficient.

Pointed versus singular Boltzmann samplers: a comparative analysis

Laboratoire d’Informatique de Paris-Nord CNRS UMR 7030 Université Paris-Nord 93430 Villetaneuse, France

Sorbonne Universités UPCM Univ. Paris 06, CNRS, LIP6 UMR 7606 75005 Paris, France

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Pointed versus singular Boltzmann samplers: a comparative analysis"}

Since the last two decades huge systems (such as giant graphs, big data structures, . . . ) have played a central role in computer science, and with the...

Pointed versus singular Boltzmann samplers: a comparative analysis

Online veröffentlicht: 24. Juni 2016

Seitenbereich: 115 - 131

Eingereicht: 10. Okt. 2014

DOI: https://doi.org/10.1515/puma-2015-0012

Schlüsselwörter
Boltzmann sampler, analysis of algorithms, analytic combinatorics

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Pointed versus singular Boltzmann samplers: a comparative analysis

Online veröffentlicht: 24. Juni 2016

Seitenbereich: 115 - 131

Eingereicht: 10. Okt. 2014

DOI: https://doi.org/10.1515/puma-2015-0012

SchlüsselwörterBoltzmann sampler, analysis of algorithms, analytic combinatorics

© 2016

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Schlüsselwörter
Boltzmann sampler, analysis of algorithms, analytic combinatorics