Tries
Speaker: Wojciech Szpankowski , Purdue University
Date: September 21 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: Digital trees have myriad applications, including the ubiquitous
family of Lempel-Ziv data compression schemes, distributed hashing,
and computational biology. Tries, introduced by de la Briandais in
1959, are digital trees that store keys, usually represented as
strings, in external nodes (leaves).
In the first part of this talk we present precise analysis of the
trie's profile which is defined as the number of external nodes with
the same distance to the root. It appears that the profile of tries
exhibits several fascinating phenomena: Near the root of a trie, the
profile is exponentially small (with the number of strings stored),
then it decays in a logarithmic rate until it abruptly starts growing,
first logarithmically, then oscillating polynomially, and finally
tending polynomially to zero again.
We next describe the average profile of another digital tree, namely
the digital search tree in which keys are stored directly in internal
nodes. As one possible application, we shall analyze a suffix trie
arising in an error resilient Lempel-Ziv'77 scheme. These studies fall
under the so called analytic information theory that applies
complex-analytic techniques to problems of information theory.
Following Hadamard's precept, we tackle these problems by such methods
as generating functions, Mellin transform, Fourier series, saddle
point method, analytic poissonization and depoissonization, and
singularity analysis.
If time allows, in the second part of the talk we move to the ``Beyond
Shannon'' territory and describe the newly established NSF Science and
Technology Center on Science of Information. Its mission is to develop
rigorous principles guiding the extraction, manipulation, and exchange
of information, integrating elements of space, time, structure,
semantics and context. This is a multi-disciplinary and
multi-institution effort that involves Purdue, Berkeley, Bryn Mawr,
Howard, MIT, Princeton, Stanford, UCSD, and UIUC.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in September 2010
