Yongwook Choi ; Charles Knessl ; Wojciech Szpankowski - A New Binomial Recurrence Arising in a Graphical Compression Algorithm

dmtcs:2979 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2979
A New Binomial Recurrence Arising in a Graphical Compression AlgorithmArticle

Authors: Yongwook Choi 1; Charles Knessl 2; Wojciech Szpankowski 3

  • 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.


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
  • Information Transfer in Biological Systems; Funder: National Science Foundation; Code: 0800568
  • 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

Consultation statistics

This page has been seen 276 times.
This article's PDF has been downloaded 189 times.