Geometric Bucket Trees: Analysis of Linear Bucket Tree

Philippe Jacquet 1 Paul Muhlethaler 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We analyse the average number of buckets in a Linear Bucket tree created by $n$ points uniformly dispatched on an interval of length $y$. A new bucket is created when a point does not fall in an existing bucket. The bucket is the interval of length 2 centered on the point. We illustrate this concept by an interesting tale of how the moon's surface took on its present form. Thanks to an explicit Laplace transform of the Poissonized sequence, and the use of dePoissonization tools, we obtain the explicit asymptotic expansions of the average number of buckets in most of the asymptotic regimes relative to $n$ and $y$.
Keywords : bucket tree
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.401-414, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01185562
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:31:51
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:56:28

Fichier

dmAM0128.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185562, version 1

Collections

X | INSMI | INRIA | PARISTECH | TDS-MACS

Citation

Philippe Jacquet, Paul Muhlethaler. Geometric Bucket Trees: Analysis of Linear Bucket Tree. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.401-414, 2010, DMTCS Proceedings. 〈hal-01185562〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

240

Téléchargements de fichiers

121

Contact


archive-ouverte@inria.fr