|
Session 27. Probabilistic and Extremal Combinatorics
|
On digital tree structures under Markov Sources |
Ralph Neininger, Goethe University Frankfurt a.M., Germany
|
The talk is based on joint works with Kevin Leckey, Henning Sulzbach and Wojtek Szpankowski
|
|
|
Digital tree structures such as digital search trees, tries and Patricia tries are fundamental combinatorial structures. As data structures they support sorting, searching and selecting within sets of data which are given as strings. In this talk the asymptotic behaviour (as the size of the data set tends to infinity) is studied in a probabilistic model where the data are independently generated from a Markov chain. This extends the well-studied Bernoulli model of strings with independent and identically distributed symbols. As applications we find the asymptotic mean, variance and limit distribution of the complexity of bucket sorting under Markov sources and corresponding asymptotics for bucket selection with various models for the rank to be selected.
|
|
| Print version |
|
