Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Digital Trees and Me ...
Conference paper

Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Philippe Flajolet (1), Mathieu Roux (2) (3), Brigitte Vallée (2)
(1) Algorithms
(2) Equipe AMACC - Laboratoire GREYC - UMR6072
(3) Laboratoire de Mathématiques Nicolas Oresme
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2799
License
https://about.hal.science/hal-authorisation-v1
Indicators
748
Views
511
Downloads

Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Philippe Flajolet (1), Mathieu Roux (2) (3), Brigitte Vallée (2)
(1) Algorithms
(2) Equipe AMACC - Laboratoire GREYC - UMR6072
(3) Laboratoire de Mathématiques Nicolas Oresme
Abstract
Digital trees, also known as $\textit{"tries''}$, are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the $\textit{memoryless source}$, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous $\textit{Dirichlet series}$. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific $\textit{arithmetic properties}$, especially irrationality measures, of the sources under consideration.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • Analysis of algorithms
  • complex asymptotics
  • digital tree
  • Mellin transform
  • memoryless sources
  • trie
Cited by

Source: OpenCitations

  • Central limit theorems for additive functionals and fringe trees in tries

    Electronic Journal of Probability

    Authors : Svante Janson ORCID

    Journal reference : Volume 27, 2022, pp.

    DOI : 10.1214/22-ejp776

  • On the Number of 2-Protected Nodes in Tries and Suffix Trees

    Discrete Mathematics & Theoretical Computer Science

    Authors : Jeffrey Gaither, Yushi Homma, Mark Sellke ORCID, Mark Daniel Ward ORCID

    Journal reference : Volume DMTCS Proceedings vol. AQ,..., 2012, pp.

    DOI : 10.46298/dmtcs.3008

  • Typical Depth of a Digital Search Tree built on a general source

    Authors : Kanal Hun, Brigitte Vallée ORCID

    Journal reference : Volume , 2013, pp. 1-15

    DOI : 10.1137/1.9781611973204.1

  • A weakly 1-stable distribution for the number of random records and cuttings in split trees

    Advances in Applied Probability

    Authors : Cecilia Holmgren ORCID

    Journal reference : Volume 43, 2011, pp. 151-177

    DOI : 10.1239/aap/1300198517

  • Towards a Realistic Analysis of Some Popular Sorting Algorithms

    Authors : J. CLÉMENT ORCID, T. H. NGUYEN THI, B. VALLÉE ORCID

    Journal reference : Volume 24, 2014, pp. 104-144

    DOI : 10.1017/s0963548314000649

  • A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms

    Authors : Clément, Nguyen Thi, Vallée

    Journal reference : Volume , 2013, pp.

    DOI : 10.4230/lipics.stacs.2013.598

  • A leader-election procedure using records

    arXiv (Cornell University)

    Authors : Gerold Alsmeyer ORCID, Zakhar Kabluchko ORCID, Alexander Marynych ORCID

    Journal reference : Volume 45, 2017, pp.

    DOI : 10.1214/16-aop1167

  • On the Variety of Shapes in Digital Trees

    arXiv (Cornell University)

    Authors : Jeffrey Gaither, Hosam Mahmoud ORCID, Mark Daniel Ward ORCID

    Journal reference : Volume 30, 2016, pp. 1225-1254

    DOI : 10.1007/s10959-016-0700-x

  • The asymptotic distribution of cluster sizes for supercritical percolation on random split trees

    arXiv (Cornell University)

    Authors : Gabriel Berzunza, Cecilia Holmgren ORCID

    Journal reference : Volume 60, 2021, pp. 631-652

    DOI : 10.1002/rsa.21046

  • The total path length of split trees

    The Annals of Applied Probability

    Authors : Nicolas Broutin, Cecilia Holmgren

    Journal reference : Volume 22, 2012, pp.

    DOI : 10.1214/11-aap812

  • Zeta functions and solutions of Falconer-type problems for self-similar subsets of ℤn

    Proceedings of the London Mathematical Society

    Authors : Driss Essouabri ORCID, Ben Lichtin

    Journal reference : Volume , 2015, pp. pdv049

    DOI : 10.1112/plms/pdv049

  • Context Trees, Variable Length Markov Chains and Dynamical Sources

    Lecture notes in mathematics

    Authors : Peggy Cénac, Brigitte Chauvin, Frédéric Paccaut ORCID, Nicolas Pouyanne

    Journal reference : Volume , 2012, pp. 1-39

    DOI : 10.1007/978-3-642-27461-9_1

  • Inversions in Split Trees and Conditional Galton–Watson Trees

    arXiv (Cornell University)

    Authors : XING SHI CAI ORCID, CECILIA HOLMGREN ORCID, SVANTE JANSON ORCID, TONY JOHANSSON ORCID, FIONA SKERMAN ORCID

    Journal reference : Volume 28, 2018, pp. 335-364

    DOI : 10.1017/s0963548318000512

  • Designing a Side Channel Resistant Random Number Generator

    Lecture notes in computer science

    Authors : Suresh N. Chari, Vincenzo V. Diluoffo, Paul A. Karger, Elaine R. Palmer, Tal Rabin ORCID, Josyula R. Rao, Pankaj Rohotgi, Helmut Scherzer, Michael Steiner ORCID, David C. Toll

    Journal reference : Volume , 2010, pp. 49-64

    DOI : 10.1007/978-3-642-12510-2_5
Preview
Loading PDF preview...