CSAIL Event Calendar: Previous Series

Asymptotic Average Profiles, from Tries to Suffix-trees

Speaker: Pierre Nicodeme , (CNRS)Laboratoire d
Date: May 22 2006
Time: 11:30AM to 1:00PM
Location: TOC Lab 32-G575
Host: P Clote-BC & B Berger- MIT

We build upon previous work of Julien Fayolle (2004) and Park and
Szpankowski (2005)
to study asymptotically the average internal profiles of tries and of
suffix-trees. The binary keys and the strings are built from a Bernoulli source $(p,q)$.
We consider the average number of internal nodes at depth $k=O(\log(n))$ of
a trie whose number of input keys (i) is a fixed number $n$
or (ii) follows a Poisson law of parameter $n$.
In both cases we obtain a summation formula with $2^k$ terms; there is
an excellent agreement of the fixed case formula for the trie and
simulations for a suffix-tree with an equivalent number of keys.
When $n$ and $k$ tend to infinity, we get rid of the summation in the
Poisson case by Mellin transform.
The inverse Mellin transform is performed by a saddle-point
integration and depoissonization by a Ramanujan expansion.
This gives, for the trie,
(a) an asymptotic estimate for the average
profile in the Poisson model,
(b) an asymptotic bound of the difference between the fixed case
and the Poisson case.
We end the proof by asymptotically bounding the difference of the profile of
trie in the Poisson model and the suffix-tree.

MIT
Department of Mathematics
& The Theory of
Computation Group
at CSAIL

See other events that are part of Bioinformatics Seminar Series 2005/2006

See other events happening in May 2006