Distribution of inter-node distances in digital trees

Abstract : We investigate distances between pairs of nodes in digital trees (digital search trees (DST), and tries). By analytic techniques, such as the Mellin Transform and poissonization, we describe a program to determine the moments of these distances. The program is illustrated on the mean and variance. One encounters delayed Mellin transform equations, which we solve by inspection. Interestingly, the unbiased case gives a bounded variance, whereas the biased case gives a variance growing with the number of keys. It is therefore possible in the biased case to show that an appropriately normalized version of the distance converges to a limit. The complexity of moment calculation increases substantially with each higher moment; A shortcut to the limit is needed via a method that avoids the computation of all moments. Toward this end, we utilize the contraction method to show that in biased digital search trees the distribution of a suitably normalized version of the distances approaches a limit that is the fixed-point solution (in the Wasserstein space) of a distributional equation. An explicit solution to the fixed-point equation is readily demonstrated to be Gaussian.
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.1-10, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184045
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:53
Dernière modification le : jeudi 11 mai 2017 - 01:03:09
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:53

Fichier

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

Identifiants

  • HAL Id : hal-01184045, version 1

Collections

Citation

Rafik Aguech, Nabil Lasmar, Hosam Mahmoud. Distribution of inter-node distances in digital trees. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.1-10, 2005, DMTCS Proceedings. 〈hal-01184045〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

73