%Random Structures and Algorithms

% Several graphics of trees are not in this version
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\input amstex
\documentstyle{amsppt}



\define\oo{\omega}
\define\ooo{\omega'}
\define\TL{\widetilde L}
\define\Tl{\widetilde l}
\define\for{\quad\text{for}\quad}
%\nologo
\redefine \and{\quad\text{and}\quad}

\topmatter
\title
MULTIDIMENSIONAL DIGITAL SEARCHING --\\
ALTERNATIVE DATA STRUCTURES
\endtitle
\author
Peter Kirschenhofer\footnote"\dag"
{This research was supported by Fonds zur F\"or\-der\-ung
der Wissenschaftlichen For\-schung Projekt No. P7497-TEC}
and Helmut Prodinger\dag
\endauthor











\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address
 TU Vienna, Wiedner Hauptstra{\ss}e 8-10, A-1040 Vienna, Austria
\endaddress



\abstract
We analyze the average cost of partial match queries
 in $M$--dimensional Digital Search Trees and Patricia Tries.
Our results allow a precise comparison of the average behaviour of these
data structures with the $M$--dimensional Tries studied by 
Flajolet and Puech \cite{1}. It turns out that Patricia is superior
to Digital Search Trees, the latter ones being superior to Tries.
\endabstract

\endtopmatter

\document

\heading
1. Introduction and Main Results
 \endheading

Random trees under the Bernoulli model occur frequently in connection with
data structures in Computer Science. In this paper we concentrate on some
aspects of {\it multidimensional search trees}.
The manipulation of {\it multidimensional data} is of vital importance
 with respect to the
construction of database systems and applications, where
we mention e.g. graphical algorithms. See Flajolet/Puech \cite 1
for an exhaustive list of references on the subject. One of the
important data structures in this context are the so--called 
$M$--dimensional tries, "$M$--tries" for short:
 
The principle of the construction of tries (and other related data
structures) is that digital properties of keys are used to build up a 
tree: In the basic case the keys are thought to be 0,1--sequences,
where 0 and 1 occur with equal probability, and the keys are stored 
in the external nodes (leaves) of a binary tree, according to their 
shortest unique prefix among the other keys. (See Knuth \cite 3
for details.)

The $M$--tries follow the same principle, but now the keys are
$M$--tuples of 0,1--sequences, e.g.
$$
\aligned
K_1&=\left(K_{11},\dots,K_{1M}\right)\\
&\vdots \\
K_N&=\left(K_{N1},\dots,K_{NM}\right)
\endaligned
$$
with all $K_{ij}$ infinite 0,1--sequences.

To build up the $M$--trie the $M$ sequences
$K_{i1},\dots,K_{iM}$
corresponding to key $K_i$ are "shuffled" to yield
{\it one} binary sequence $K'_i$, and the sequences
$K'_1,\dots,K'_N$ are used to build up  a regular trie:

More precisely, if 
$K_{ij}=\left(K_{ij}^{(0)},K_{ij}^{(1)},K_{ij}^{(2)},\dots\right)$,
then
$$K'_i=\left(K_{i1}^{(0)},\dots,K_{iM}^{(0)},K_{i1}^{(1)},\dots,K_{iM}^{(1)},
K_{i1}^{(2)},\dots\right).
$$
\proclaim{Example} M=2
\endproclaim
$$
\aligned
K_1=(01\dots\ ,\ 00\dots)&\longrightarrow K'_1=(0010\dots)\\
K_2=(10\dots\ ,\ 01\dots)&\longrightarrow K'_2=(1001\dots)\\
K_3=(11\dots\ ,\ 00\dots)&\longrightarrow K'_3=(1010\dots)\\
\endaligned
$$
\vskip 2 cm
2--trie:
\vskip 3 cm

A {\it partial match query} $q$ asks for all records whose
attributes are either specified or not: If e.g.
$q=(*,100\cdots)$, we look for items with unspecified first
component, and second component equal to $100\cdots$.
The {\it specification pattern} of a query in an $M$--trie is
a word in $\{S,*\}^{M}$, where $S$ stands for a specified component
and $*$ for an unspecified one; in our example we have the pattern
$*S$.

A measure for the {\it cost of a query} is the number of internal
nodes visited during the search. In \cite 1 a precise analysis
of the average cost
$l^{[T]}_{\omega,N}$ of a query of pattern $\omega$ in an $M$--trie
built from $N$ random keys has been presented.
Throughout this paper the underlying probability model is the
{\it Bernoulli model}.

\proclaim{Theorem T} {\rm(\cite 1)}
$$
\aligned
l^{[T]}_{\omega,N}\sim N^{1-\frac sM}\cdot\Bigg\{
&
\frac{s}{M^2L}\cdot\frac{\Gamma\left(\frac sM\right)}{1-\frac sM}\cdot
\sum_{j=0}^{M-1}\left(\delta_1\delta_2\dots\delta_j\right)
2^{-j\left(1-s/M\right)}\\
&+\delta_\omega^{[T]}\left(\log_2N^{1/M}\right)\Bigg\},
\endaligned
$$
where $s$ is the number of specified attributes in $\omega$, $1\le s\le M-1$,
$L=\log 2$, $\delta_i= 1$ resp. 2 according to the $i$--th attribute
in $\omega$ being specified resp. unspecified, and
$\delta_\omega^{[T]}\left(x\right)$ a continuous periodic function
of mean zero with small amplitude.\qed
\endproclaim

Similar results have been developed in \cite 1 for binary search trees
and grid file algorithms.
\medskip

The aim of our paper is twofold: On the one hand we want to establish
 results like Theorem T for the $M$--dimensional versions of 
other prominent data
structures, namely: Digital Search Trees, Patricia Tries and
$b$--tries. (See \cite 3 for the definitions.)
On the other hand we also present an alternative approach for gaining
the asymptotic results in the analysis.
In the following we give a survey of our main results.
More details and sketches of the derivations may be found in the following 
sections.

In the case of $M$--dimensional {\it Digital Search Trees} 
($M$--DST for short), we follow the construction principle of
$M$--tries, but storing the records in the
internal nodes of a binary tree according to the order of their
appearance.

\proclaim{Example} With $K_1,K_2,K_3$ from  the last example
we get the 2--DST
\vskip 4.5 cm
\endproclaim

The cost of a query is again measured by the number of nodes visited
during the search. Adopting an analogous notation to Theorem T,
our result reads:

\proclaim{Theorem D} 
$$
\aligned
l^{[D]}_{\omega,N}\sim N^{1-\frac sM}\cdot\Bigg\{
&
\frac{Q\left(2^{1-\frac sM}\right)}{Q_\infty}\cdot\frac{1}{ML}\cdot
\frac{\Gamma\left(\frac sM\right)}{1-\frac sM}\times\\
&\times\sum_{j=0}^{M-1}\left(\delta_1\delta_2\dots\delta_j\right)
2^{-j\left(1-s/M\right)}\\
&+\delta_\omega^{[D]}\left(\log_2N^{1/M}\right)\Bigg\},
\endaligned
$$
where $Q(t)=\prod\limits_{j\ge 1}\left(1-\frac{t}{2^j}\right)$ and 
$Q_\infty=Q(1)$.
\qed
\endproclaim

The basic idea of {\it Patricia Tries} is to compress
one--way branches in Tries:


\proclaim{Example} With $K_1,K_2,K_3$ from  above
we get the 2--Patricia Trie
\vskip 4.5 cm
\endproclaim

Our result for this instance is

\proclaim{Theorem P}
$$
\aligned
l^{[P]}_{\omega,N}\sim N^{1-\frac sM}\cdot\Bigg\{
&
\left(\frac sM+1\right)\cdot\left(1-2^{-s/M}\right)\cdot
\frac{1}{ML}\cdot\frac{\Gamma\left(\frac sM\right)}{1-\frac sM}\times\\
&\times
\sum_{j=0}^{M-1}\left(\delta_1\delta_2\dots\delta_j\right)
2^{-j\left(1-s/M\right)}\\
&+\delta_\omega^{[P]}\left(\log_2N^{1/M}\right)\Bigg\}.\ \qed
\endaligned
$$
\endproclaim


Theorems T, D and P allow a precise comparison of the average cost of 
partial match queries in the concerned data structures: Neglecting
the small periodic fluctuations the 
\vskip 0.4 cm
{\smc Comparison Inequality}
$$
(1+x)\left(1-2^{-x}\right)<
\frac{Q\left(2^{1-x}\right)}{Q_\infty}<x\for 0<x<1
$$
ensures that
$$
l_{\omega,N}^{[P]}\ \preceq \ l_{\omega,N}^{[D]}\ \preceq \ 
l_{\omega,N}^{[T]}
$$
for all query patterns $\omega$. In Section 5 we give a proof of this
comparison result.


The reader should be aware of the fact that the average
cost of a partial match query is some sort of mixture
of the cost of successful and unsuccessful search in the
corresponding digital trees and compare the above result with
Knuth's results on the latter parameters in \cite 3.

In the following table we present the constants in question
for the instance $M=2$ and the two possible query patterns $\omega_1=*S$ and
$\omega_2=S*$: (In both cases we have $s=1$, so that the order of
$l_N$ is $\sqrt N$.)

\bigskip
$$
\alignat{ 4}
&&&\ \  T&\qquad&\ \   D &\qquad& \ \  P\\
\omega_1&=*S &\qquad 3&.0867\dots&\qquad 2&.7768\dots&\qquad2&.7122\dots\\
\omega_2&=S* &\qquad 2&.1826\dots&\qquad 1&.9635\dots&\qquad     
1&.9178\dots
\endalignat
$$

\bigskip

In the final section  we deal with $M$--dimensional tries, where
each external node can keep up to $b$ records. If we measure the
cost of a query as with $M$--tries we get

\proclaim{Theorem B} 
$$
\aligned
l^{[B]}_{\omega,N}\sim N^{1-\frac sM}\cdot\Bigg\{
&
\binom{\frac sM+b-1}{b}\cdot
\frac{1}{ML}\cdot\frac{\Gamma\left(\frac sM\right)}{1-\frac sM}\times\\
&\times\sum_{j=0}^{M-1}\left(\delta_1\delta_2\dots\delta_j\right)
2^{-j\left(1-s/M\right)}\\
&+\delta_\omega^{[B]}\left(\log_2N^{1/M}\right)\Bigg\}.\ \qed
\endaligned
$$
\endproclaim

This result can be compared with the result for grid--file--algorithms
in Flajolet/Puech \cite 1, where they use the {\it same data structure}
but a {\it different cost measure}.

\bigskip

\heading
2. Digital Search Trees
\endheading

Let $\oo$ be a fixed query pattern and $\ooo$ the (cyclic) shift
of $\oo$, i.e. for $\oo=w_1w_2\dots w_M$ we have $\ooo=w_2\dots w_Mw_1$.
Obviously, $\oo^{(M)}=\oo$.
We further denote the probability generating function for the cost
with query pattern $\oo$ and $N$ records by $H_{\oo,N}(z)$.
From the construction of the $M$--dimensional Digital Search Trees in 
Section 1, we find immediately the following pair of recursions 
(the reader should remember that we always consider the Bernoulli model):
$$
H_{\oo,N+1}(z)=z\sum_{k=0}^N2^{-N}\binom Nk H_{\ooo,k}(z)\cdot\left\{
\aligned
&H_{\ooo,N-k}(z)\for \oo=*\nu\\
&1\qquad \qquad\ \for \oo=S\nu
\endaligned
\right.
$$
for $N\ge 0$, $H_{\oo,0}(z)=1$.

The expectations of cost $l_{\oo,N}=l_{\oo,N}^{[D]}$ are given by
$H'_{\oo,N}(1)$, so that the recursion translates into
$$
l_{\oo,N+1}=1+\delta_12^{-N}\sum_{k=0}^N\binom Nkl_{\ooo,k},
\for N\ge 0, \quad l_{\oo,0}=0,
$$
where $\delta_i=2$ resp. 1 referring to $w_i=*$ resp. $S$ in $\oo$.

Thus the exponential generating functions 
$$
L_{\oo}(z)=\sum_{N\ge 0}l_{\oo,N}\frac{z^N}{N!}
$$
fulfill the differential--functional equations
$$
L'_{\oo}(z)=e^z+\delta_1e^{z/2}L_{\ooo}\left(\frac z2\right).
$$
In order to solve it is convenient to introduce
$$
\TL_\oo(z)=e^{-z}L_\oo(z),
$$
so that
$$
\TL'_\oo(z)+\TL_\oo(z)=1+\delta_1\TL_{\ooo}\left(\frac z2\right).
$$
Comparing coefficients we find
$$
\Tl_{\oo,N+1}=-\left(\Tl_{\oo,N}-\delta_12^{-N}\,\Tl_{\ooo,N}\right)
,\ \ N\ge 1
$$
with $\Tl_{\oo,0}=0$, $\Tl_{\oo,1}=1$.
This recurrence has the solution
$$
\Tl_{\oo,N+1}=(-1)^N
\bigg(
\prod_{j=1}^N\left(1-2^{-j}t\right)
\bigg)
\Bigg|_{t^r\to
\delta_1\delta_2\dots\delta_r}=:(-1)^NQ_{\oo,N}
$$
where $\delta_{A\cdot M+r}=\delta_r$.

We finally get the explicit solution
$$
l_{\oo,N}^{[D]}=-\sum_{k=1}^N\binom Nk (-1)^kQ_{\oo,k-1}.
$$

The asymptotic behaviour of an alternating sum of this type may be 
determined either by using the Mellin transform (this technique is used
by Flajolet and Puech in \cite 1) or, alternatively, by applying
the following Lemma from the calculus of finite
differences. (Compare \cite 2, \cite 4.)

\proclaim{Lemma } 
 Let $\Cal C$ be a
path surrounding the points $j,j+1,\dots,N$ and $f(z)$ be analytic
inside $\Cal C$ and continuous on $\Cal C$. Then
$$
\sum_{k\ge j} \binom Nk (-1)^kf(k)=-\frac 1{2\pi i}
\int_{\Cal C} [N;z]f(z)dz 
$$
with $[N;z]=\frac{(-1)^{N-1}N!}{z(z-1)\dots (z-N)}.\qed
$
\endproclaim

Moving the contour of
integration, one can obtain the asymptotic expansion of the alternating sum
by Cauchy's residue theorem:
Under certain growth conditions for $f(z)$, which are fulfilled in
our instance,
$$
\sum_{k\ge j} \binom Nk (-1)^k f(k)
$$
may be asymptotically evaluated by
$$
\sum\text{Res}
\bigl([N;z]f(z)\bigr)
$$ 
where the sum is taken over the set of
poles $z$ different from $j,j+1,$\linebreak $\dots ,N$.

In our instance we have
$$
f(k)=Q_{\oo,k-1},
$$
so that we need an analytic continuation of this discrete sequence.
Omitting the details the idea is as follows:

Using partial fraction decomposition we have
$$
\prod_{j=1}^N\left(1-2^{-j}t\right)=\frac{Q(t)}{Q_\infty}
\sum_{i\ge1}a_i\frac{1}{1-t2^{-i-N}}
$$
where 
$$Q(t)=\prod_{j\ge1}\left(1-2^{-j}t\right), \ Q_\infty=Q(1)
\and a_i=(-1)^{i-1}2^{-\binom i2}/Q_{i-1}.
$$
Using Euler's product identity
$$
Q(t)=\sum_{n\ge0}a_{n+1}t^n
$$
and expanding the geometric series in $t$ we get
$$
\prod_{j=1}^N\left(1-2^{-j}t\right)
=\frac{1}{Q_\infty}\sum_{m\ge 0}
t^m
\sum_{i\ge1}a_i
\sum_{r=0}^m
a_{m-r+1}2^{-r(N+i)}.
$$
Since this is an identity for analytic functions in $t$,
the coefficients of $t^m$ must coincide, and we are allowed to substitute
$t^m$ by $\delta_1\dots \delta_m$ in both sides, simultanously.
We get
$$
Q_{\oo,N}=\frac{1}{Q_\infty}
\sum_{m\ge 0}\delta_1\dots \delta_m\sum_{i\ge1}a_i\sum_{r=0}^m
a_{m-r+1}2^{-r(N+i)}.
$$
Now, for $m=A\cdot M+j$,
$$
\delta_1\dots \delta_m=2^{A(M-s)}\cdot \delta_1\dots \delta_j
$$
so that, after rearranging the sums,
$$
\aligned
Q_{\oo,N}=\frac{1}{Q_\infty}\sum_{j=0}^{M-1}\delta_1\dots \delta_j
&\sum_{i\ge1}a_i
\sum_{h\ge 0}a_{h+1}2^{(h-j)(N+i)}\times\\
&\times\sum_{A\ge \max\left(0,\frac{h-j}{M}\right)}
2^{-A(M(N+i-1)+s)}
\endaligned
$$
and, by replacing $N$ by $z$, we have
$$
\aligned
&Q_{\oo,z}=\frac{1}{Q_\infty}
\sum_{j=0}^{M-1}\delta_1\dots \delta_j
\sum_{i\ge1}a_i
\frac{1}{1-2^{-M(z+i-1)-s}}\times\\
&\times\left\{
\sum_{h= 0}^{j-1}a_{h+1}2^{(h-j)(z+i)}
+\sum_{h\ge j}a_{h+1}2^{(h-j)(z+i)-\lceil \frac{h-j}{M}\rceil
\cdot (M(z+i-1)-s)}\right\}.
\endaligned
$$

Using the Lemma from above we have to look for the residues
of $[N;z]\cdot Q_{\oo,z-1}$ with real part $<1$: The dominating
singularity is the first order pole $z=1-\frac sM$, which
occurs for $i=1$ in the above expression for
$Q_{\oo,z-1}$ , and the residue can be calculated to be

$$
\left[N;1-\frac sM\right]\frac{1}{Q_\infty}\sum_{j=0}^{M-1}
\delta_1\dots \delta_j\sum_{h\ge 0}a_{h+1}2^{(h-j)\left(1-\frac sM\right)}
\cdot\frac{1}{ML}
$$
($L=\log 2$). Using again Euler's product identity we get
$$
\left[N;1-\frac sM\right]\frac{1}{Q_\infty}\sum_{j=0}^{M-1}
\delta_1\dots \delta_j\,
2^{-j\left(1-\frac sM\right)}Q\left(2^{1-\frac sM}\right)
\frac{1}{ML}.
$$
Since
$$
\aligned
\left[N;1-\frac sM\right]
&=\Gamma\left(-1+\frac sM\right)\cdot 
\Gamma(N+1)\Big/\Gamma\left(N+\frac sM\right)\\
&\sim N^{1-\frac sM}\cdot \Gamma\left(-1+\frac sM\right)
\endaligned
$$
we get the main term in Theorem D.

The periodic fluctuation $\delta_\oo^{[D]}$ originates from the
simple poles at \linebreak
$1-\frac sM+\frac{2k\pi i}{LM}$; in principle one can
get the Fourier expansion of $\delta_\oo^{[D]}(x)$ by collecting
the
residues at these poles, but we omit the details here.

\bigskip

\heading
3. Patricia Tries
\endheading

With the notations of Section 2 we may proceed with this instance as
follows: The probability generating functions of cost fulfill
for $N\ge2$
$$
\aligned
H_{\oo,N}(z)&=z\sum_{k=0}^N2^{-N}\binom Nk H_{\ooo,k}(z)\cdot\left\{
\aligned
&H_{\ooo,N-k}(z)\\
&1 
\endaligned
\right\}\\
&-(z-1)\delta_1\, 2^{-N}H_{\ooo,N}(z),
\endaligned
$$
$H_{\oo,0}(z)=H_{\oo,1}(z)=1$.

The subtraction terms correspond to the compression of ordinary
tries as indicated in the Introduction.

The average costs are given by
$$
l_{\oo,N}=1-\delta_12^{-N}+\delta_12^{-N}\sum_{k=0}^N\binom Nkl_{\ooo,k}
$$
for $N\ge2$.

This time the functions $\TL_\oo(z)$ fulfill
a system of functional equations
$$
\TL_\oo(z)=g_1(z)+\delta_1\TL_{\ooo}\left(\frac z2\right),
$$
where
$$
g_i(z)=1-(1+z)e^{-z}-\delta_i\left(e^{-z/2}-\left(1+\frac z2\right)
e^{-z}\right).
$$
The system may be solved by iteration and gives us
$$
\Tl_{\oo,N}=\frac{1}{1-2^{M\left(1-N-s/M\right)}}
\sum_{j=0}^{M-1}\delta_1\dots \delta_j \, 2^{-jN}
\left[\frac{z^N}{N!}\right]g_{j+1}(z).
$$
Now
$$
\left[\frac{z^N}{N!}\right]g_{j+1}(z)
=(-1)^N
\left(N-1-\delta_{j+1}\left(2^{-N}+\frac N2-1\right)\right),
$$
so that
$$
l_{\oo,N}=\sum_{k=1}^N\binom Nk(-1)^kf(k)
$$
with
$$
\aligned
f(z)&=\frac{1}{1-2^{M\left(1-z-s/M\right)}}\times\\
&\times\sum_{j=0}^{M-1}\delta_1\dots \delta_j \, 2^{-jz}
\left(z-1-\delta_{j+1}\left(2^{-z}+\frac z2-1\right)\right).
\endaligned
$$
Collecting the residues of $[N;z]f(z)$ at $z=1-s/M$ we get the main
contribution
$$
\aligned
N^{1-\frac sM}\cdot\frac{-1}{ML}
\Gamma\left(\frac sM-1\right)
&\sum_{j=0}^{M-1}\delta_1\dots \delta_j \, 2^{-j\left(1-s/M\right)}\times\\
&\times
\left[\frac sM-\frac{\delta_{j+1}}{2}\left(1+\frac sM-2^{s/M}\right)\right].
\endaligned
$$
The sum can be rearranged as follows:
$$
\aligned
&\sum_{j=0}^{M-1}\delta_1\dots \delta_j\, 
2^{-j\left(1-s/M\right)}\cdot\frac sM\\
&-\frac 12\sum_{j=1}^{M}\delta_1\dots \delta_j\, 
2^{-j\left(1-s/M\right)}\cdot
2^{1-s/M}\left(1+\frac sM-2^{s/M}\right)\\
&=\sum_{j=1}^{M-1}\delta_1\dots \delta_j\, 
2^{-j\left(1-s/M\right)}\cdot
\left(\frac sM -2^{-s/M}\left(1+\frac sM-2^{s/M}\right)\right)\\
&+\frac sM-\frac 122^{M-s-M\left(1-s/M\right)+1-s/M}
\left(1+\frac sM-2^{s/M}\right)
,\endaligned
$$
since
$\delta_1\dots \delta_M=2^{M-s}$, and furthermore
$$
=\left(\frac sM+1\right)\left(1-2^{-s/M}\right)
\sum_{j=0}^{M-1}\delta_1\dots \delta_j\, 
2^{-j\left(1-s/M\right)}.
$$

From the last observation Theorem P is immediate.

\bigskip

\heading
5. The Comparison Inequality
\endheading

Let $f(x)=Q\left(2^{-x}\right)/Q_\infty$. It is easily seen that the
left--hand side of the inequality is equivalent to 
$$
1+x<f(x) \for 0<x<1 \tag i
$$
and the right--hand side to 
$$
f(x)<1+x \for -1<x<0. \tag ii
$$
Now
$$
f(x)=\prod_{j\ge 1}\left(1+\frac{1-2^{-x}}{2^j-1}\right)=P(y)
$$
where $y=1-2^{-x}$ fulfills (i) $0<y<\frac 12$ resp. (ii)
$-1<y<0$.

Let
$$
g(y)=\frac{1+x}{f(x)}=\frac{1-\log_2(1-y)}{P(y)}.
$$
Since $g(0)=g\left(\frac 12\right)=1$, it is sufficient to prove that $g(y)$
is a logarithmically convex function in $y$ for $-1<y<\frac 12$:
With $h(y)=\log g(y)$ we find
$$
h^{''}(y)=\frac{1}{\left(1-y\right)^2}\cdot
\left\{\frac{1}{\log\left(\frac{2}{1-y}\right)}
-\frac{1}{\log^2\left(\frac{2}{1-y}\right)}+
\sum_{j\ge 1}\left(\frac{2^j}{1-y}-1\right)^{-2}\right\}.
$$
The expression in brackets should be positive, which is
(with $z=1+x=1-\log_2(1-y)$) equivalent to
$$
\sum_{j\ge0}\left(2^{j+z}-1\right)^{-2}
>\frac{1}{L^2z^2}-\frac 1{Lz}, \quad 0<z<2.
$$
The last inequality is trivial for $z\ge 1/L$, since the 
right--hand side is $<0$,
and is {\it a fortiori} proved for $0<z<1/L$ by
$$
\left(\frac{2^z-1}{Lz}\right)^2<\frac{1}{1-Lz},
$$
which may be seen directly by comparing the Taylor coefficients
of both sides.
\bigskip


\heading
6. $b$--Tries
\endheading

Here we have for the probability generating function
$$
H_{\oo,N}(z)=z\sum_{k=0}^N2^{-N}\binom Nk H_{\ooo,k}(z)\cdot\left\{
\aligned
&H_{\ooo,N-k}(z)\\
&1
\endaligned
\right\}
$$
for $N\ge b+1$, $H_{\oo,0}(z)=\dots=H_{\oo,b}(z)=1$.

The functional equations for $\TL_{\oo}(z)$ read
$$
\TL_{\oo}(z)=1-e_b(z)\cdot e^{-z}+\delta_1
\TL_{\ooo} \left(\frac z2\right)
$$
where
$$
e_b(z)=\sum_{i=0}^b\frac{z^i}{i!}.
$$
Iteration of the system and comparing coefficients yields
$$
l_{\omega,N}=\sum_{k=1}^N\binom Nk(-1)^kf(k)
$$
with
$$
f(z)=\frac{(-1)^{b+1}\binom{z-1}b}{1-2^{M\left(1-z-s/M\right)}}
\sum_{j=0}^{M-1}\delta_1\dots\delta_j\, 2^{-jz}.
$$
Calculating the residues at the dominating poles we find Theorem B
by some easy manipulations.

\bigskip

\Refs

\ref \no 1 \by P. Flajolet, C. Puech \paper Partial match
retrieval of multidimensional data \jour Journal ACM \vol 33
\yr 1986 \pages 371--507 \endref

\ref \no 2 \by P.Flajolet, R.Sedgewick \paper Digital Search Trees Revisited
\jour SIAM J. Comput. \vol 15 \yr 1986 \pages 748--767 \endref

\ref \no 3  \by D. E. Knuth \book The Art of Computer Programming,
Vol. 3 \publ Addison-Wesley \yr 1973 \endref

\ref \no 4 \by N.E.N\"orlund \book Vorlesungen \"uber Differenzenrechnung
\publ Chelsea \publaddr New York \yr 1954 \endref

\endRefs

\enddocument
