Discrete Mathematics & Theoretical Computer Science |

2979

- 1 J. Craig Venter Institute
- 2 Department of Mathematics, Statistics and Computer Science [Chicago]
- 3 Department of Computer Science [Purdue]

In a recently proposed graphical compression algorithm by Choi and Szpankowski (2009), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability $p$) or the right subtree (with probability 1-$p$). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer $d$ is given, and at level $d$ or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after $n+d$ steps). Observe that when $d=∞$ the above tree can be modeled as a $\textit{trie}$ that stores $n$ independent sequences generated by a memoryless source with parameter $p$. Therefore, we coin the name $(n,d)$-tries for the tree just described, and to which we often refer simply as $d$-tries. Parameters of such a tree (e.g., path length, depth, size) are described by an interesting two-dimensional recurrence (in terms of $n$ and $d$) that – to the best of our knowledge – was not analyzed before. We study it, and show how much parameters of such a $(n,d)$-trie differ from the corresponding parameters of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.

Source: HAL:hal-01197247v1

Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Section: Proceedings

Published on: January 1, 2012

Imported on: January 31, 2017

Keywords: Digital trees,Mellin transform,poissonization,graph compression,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Funding:

- Source : OpenAIRE Graph
*Emerging Frontiers of Science of Information*; Funder: National Science Foundation; Code: 0939370*Collaborative Research: Information Theory of Data Structures*; Funder: National Science Foundation; Code: 0830140*Information Transfer in Biological Systems*; Funder: National Science Foundation; Code: 0800568

This page has been seen 181 times.

This article's PDF has been downloaded 133 times.