Profiles of tries
G Park, HK Hwang, P Nicodeme… - SIAM Journal on …, 2009 - SIAM
Tries (from re trie val) are one of the most popular data structures on words. They are
pertinent to the (internal) structure of stored words and several splitting procedures used in …
pertinent to the (internal) structure of stored words and several splitting procedures used in …
Asymptotic variance of random symmetric digital search trees
Asymptotic variance of random symmetric digital search trees Page 1 Discrete Mathematics and
Theoretical Computer Science DMTCS vol. 12:2, 2010, 103–166 Asymptotic variance of …
Theoretical Computer Science DMTCS vol. 12:2, 2010, 103–166 Asymptotic variance of …
[HTML][HTML] An analytic approach to the asymptotic variance of trie statistics and related structures
We develop analytic tools for the asymptotics of general trie statistics, which are particularly
advantageous for clarifying the asymptotic variance. Many concrete examples are discussed …
advantageous for clarifying the asymptotic variance. Many concrete examples are discussed …
The Wiener index of random digital trees
M Fuchs, CK Lee - SIAM Journal on Discrete Mathematics, 2015 - SIAM
The Wiener index has been studied for simply generated random trees, nonplane unlabeled
random trees, and a huge subclass of random grid trees containing random binary search …
random trees, and a huge subclass of random grid trees containing random binary search …
Limiting distributions for the costs of partial match retrievals in multidimensional tries
W Schachinger - Random Structures & Algorithms, 2000 - Wiley Online Library
In this paper we derive limiting distributions for the costs of partial match retrievals in K‐d
tries. We confine ourselves to the binary case (ie, the alphabet, from which the letters of the …
tries. We confine ourselves to the binary case (ie, the alphabet, from which the letters of the …
[HTML][HTML] On 2-protected nodes in random digital trees
In this paper, we consider the number of 2-protected nodes in random digital trees. Results
for the mean and variance of this number for tries have been obtained by Gaither et …
for the mean and variance of this number for tries have been obtained by Gaither et …
Towards more realistic probabilistic models for data structures: The external path length in tries under the Markov model
K Leckey, R Neininger, W Szpankowski - … of the Twenty-Fourth Annual ACM …, 2013 - SIAM
Tries are among the most versatile and widely used data structures on words. They are
pertinent to the (internal) structure of (stored) words and several splitting procedures used in …
pertinent to the (internal) structure of (stored) words and several splitting procedures used in …
A General Central Limit Theorem for Shape Parameters of -ary Tries and PATRICIA Tries
M Fuchs, CK Lee - The Electronic Journal of Combinatorics, 2014 - combinatorics.org
Tries and PATRICIA tries are fundamental data structures in computer science with
numerous applications. In a recent paper, a general framework for obtaining the mean and …
numerous applications. In a recent paper, a general framework for obtaining the mean and …
Profile of tries
G Park, HK Hwang, P Nicodème… - LATIN 2008: Theoretical …, 2008 - Springer
The profile of a trie, the most popular data structures on words, is a parameter that
represents the number of nodes (either internal or external) with the same distance to the …
represents the number of nodes (either internal or external) with the same distance to the …
Asymptotic normality of recursive algorithms via martingale difference arrays
W Schachinger - Discrete Mathematics & Theoretical …, 2001 - dmtcs.episciences.org
We propose martingale central limit theorems as an tool to prove asymptotic normality of the
costs of certain recursive algorithms which are subjected to random input data. The …
costs of certain recursive algorithms which are subjected to random input data. The …