HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Geometric Bucket Trees: Analysis of Linear Bucket Tree

Philippe Jacquet 1 Paul Mühlethaler 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
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:31:51 PM
Last modification on : Friday, February 4, 2022 - 3:20:21 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:56:28 AM


Publisher files allowed on an open archive




Philippe Jacquet, Paul Mühlethaler. Geometric Bucket Trees: Analysis of Linear Bucket Tree. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.401-414, ⟨10.46298/dmtcs.2764⟩. ⟨hal-01185562⟩



Record views


Files downloads