A Note on the Asymptotic Behavior of the Height in b-Tries for b Large

Get BibTex-formatted data

Download

PDF

Author

Charles Knessl, Wojciech Szpankowski

Tech report number

CERIAS TR 2002-04

Entry type

article

Abstract

We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to b items (the so called b-tries). We assume that such a tree is build from n random strings (items) generated by an unbiased memoryless source. In this paper, we discuss the case when b and n are both large. We shall identify six natural regions of the height distribution that should be compared to three regions obtained for fixed b. We prove that for most n, the limiting distribution is concentrated at the single point k1 = [log2 (n/b)] + 1 as n,b approach infinity. We observe that this is quite different than the height distribution for fixed b, in which case the limiting distribution is of an extreme value type concentrated arount (1 + 1/b)log2 n. We derive our results by analytic methods, namely generating functions and the saddle point method. We also present some numerical verification of our results.

Download

PDF

URL

https://www.cerias.purdue.edu/papers/archive/2002-04.ps

Institution

Purdue Univeristy

Journal

Electornic Journal of Combinatorics

Key alpha

Knessl

Volume

7, R39

Publication Date

1900-01-01

Copyright

2000

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Knessl,
	title = "A Note on the Asymptotic Behavior of the Height in b-Tries for b Large",
	author = "Charles Knessl, Wojciech Szpankowski",
	institution = "Purdue Univeristy",
	journal = "Electornic Journal of Combinatorics",
	volume = "7, R39",
	abstract = "We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to b items (the so called b-tries).  We assume that such a tree is build from n random strings (items) generated by an unbiased memoryless source.  In this paper, we discuss the case when b and n are both large.  We shall identify six natural regions of the height distribution that should be compared to three regions obtained for fixed b.  We prove that for most n, the limiting distribution is concentrated at the single point k1 = [log2 (n/b)] + 1 as n,b approach infinity.  We observe that this is quite different than the height distribution for fixed b, in which case the limiting distribution is of an extreme value type concentrated arount (1 + 1/b)log2 n.  We derive our results by analytic methods, namely generating functions and the saddle point method.  We also present some numerical verification of our results.",
	copyright = "2000",
	url = "https://www.cerias.purdue.edu/papers/archive/2002-04.ps",
}