| author: | Rafik Aguech, Nabil Lasmar and Hosam Mahmoud |
|---|---|
| title: | Distribution of inter-node distances in digital trees |
| keywords: | Random trees, recurrence, Mellin transform, poissonization, fixed point, contraction method. |
| 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. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Rafik Aguech and Nabil Lasmar and Hosam Mahmoud (2005), Distribution of inter-node distances in digital trees, in 2005 International Conference on Analysis of Algorithms, Conrado Martínez (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AD, pp. 1-10 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAD0101.ps.gz (80 K) |
| ps-source: | dmAD0101.ps (189 K) |
| pdf-source: | dmAD0101.pdf (102 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.