TY - GEN
T1 - Expected external profile of PATRICIA tries
AU - Magner, Abram
AU - Knessl, Charles
AU - Szpankowski, Wojciech
N1 - Publisher Copyright: © Copyright (2014) by SIAM: Society for Industrial and Applied Mathematics. All rights reserved.
PY - 2014
Y1 - 2014
N2 - We consider PATRICIA tries on n random binary strings generated by a memoryless source with parameter p ≥ 1\2. For both the symmetric (p = 1/2) and asymmetric cases, we analyze asymptotics of the expected value of the external profile at level κ = κ(n), defined to be the number of leaves at level κ. We study three natural ranges of κ with respect to n. For κ bounded, the mean profile decays exponentially with respect to n. For κ growing logarithmically with n, the parameter exhibits polynomial growth in n, with some periodic fluctuations. Finally, for κ = Θ(n), we see super-exponential decay, again with periodic fluctuations. Our derivations rely on analytic techniques, including Mellin transforms, analytic depoissonization, and the saddle point method. To cover wider ranges of k and n and provide more intuitive insights, we also use methods of applied mathematics, including asymptotic matching and linearization.
AB - We consider PATRICIA tries on n random binary strings generated by a memoryless source with parameter p ≥ 1\2. For both the symmetric (p = 1/2) and asymmetric cases, we analyze asymptotics of the expected value of the external profile at level κ = κ(n), defined to be the number of leaves at level κ. We study three natural ranges of κ with respect to n. For κ bounded, the mean profile decays exponentially with respect to n. For κ growing logarithmically with n, the parameter exhibits polynomial growth in n, with some periodic fluctuations. Finally, for κ = Θ(n), we see super-exponential decay, again with periodic fluctuations. Our derivations rely on analytic techniques, including Mellin transforms, analytic depoissonization, and the saddle point method. To cover wider ranges of k and n and provide more intuitive insights, we also use methods of applied mathematics, including asymptotic matching and linearization.
KW - Analysis of algorithms
KW - Analytic combinatorics
KW - Digital trees
KW - Generating functions
KW - Linearization
KW - Matched asymptotics
KW - Mellin transform
KW - PATRICIA trie
KW - Poissonization
KW - Recurrences
KW - Saddle point method
KW - Tree profiles
UR - https://www.scopus.com/pages/publications/84943616861
U2 - 10.1137/1.9781611973204.2
DO - 10.1137/1.9781611973204.2
M3 - Conference contribution
T3 - 11th Workshop on Analytic Algorithmics and Combinatorics 2014, ANALCO 2014
SP - 16
EP - 24
BT - 11th Workshop on Analytic Algorithmics and Combinatorics 2014, ANALCO 2014
PB - Society for Industrial and Applied Mathematics Publications
T2 - 11th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2014
Y2 - 6 January 2014
ER -