\documentstyle[12pt]{article}
\newtheorem{Proposition}{Proposition}
\newtheorem{Theorem}{Theorem}
\newtheorem{Lemma}{Lemma}
\newenvironment{pic}[1]%
{\input{#1}\begin{figure}\centerline{\box\graph}\vspace*{\bigskipamount}}%
{\end{figure}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\baselinestretch}{1.3}
\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newcommand{\con}{\rightarrow}
\newcommand{\cd}{\mbox{$\stackrel{d}{\rightarrow}$}}
\newcommand{\cp}{\mbox{$\stackrel{p}{\rightarrow}$}}
\newcommand{\ed}{\mbox{$ \ \stackrel{d}{=}$ \ }}
\newcommand{\ep}{\varepsilon}
\newcommand{\FF}{{\cal F}}
\newenvironment{singlespace}
{\def\baselinestretch{1.0}\large\normalsize}{\par}
\newenvironment{singlespace2}
{\def\baselinestretch{1.0}
\large
\normalsize
}{\par\vskip -1mm}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in}
\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\t{\widetilde}
\def\half{{1\over 2}}
\def\med{\medskip\parsec}
\def\binom Nk{{N \choose k}}
\def\C{{\cal C}}
\def\n{\eta}
\def\ss{\sigma}
\def\pr{{\rm Pr}}
\def\w{\omega}
\def\l{\ell}
\def\b{{\bf b}}
\def\d{\delta}
\def\eps{\varepsilon}
\def\GG{\Gamma}
\def\w{\omega}
\def\wo{\omega'}
\def\TL{\widetilde{L}}
\def\Tl{\widetilde{l}}
\def\TW{\widetilde{W}}
\def\Tw{\widetilde{w}}
\def\TT{\widetilde{T}}
\def\Tt{\widetilde{t}}
\def\TR{\widetilde{R}}
\def\Tr{\widetilde{r}}
\def\TM{\widetilde{M}}
\def\Tm{\widetilde{m}}
\def\sech{\text{sech}}
\vsize=8.5in
\voffset=-0.7in
\hoffset=-0.7in
\begin{document}
\begin{center}
{\bf MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS
IN TRIES}
\par
\medskip
\parsec
\today
\end{center}
\par
\bigskip\bigskip\bigskip
\begin{singlespace}
\noi
\begin{tabular}{lll}
Peter Kirschenhofer\footnotemark&Helmut Prodinger\footnotemark&Wojciech Szpankowski\footnotemark\\
Dept. of Algebra\&Discrete Math.&Dept. of Algebra\&Discrete Math.&Dept. of Computer Science\\
Technical University of Vienna&Technical University of Vienna&Purdue University\\
Vienna A-1040&Vienna A-1040&W. Lafayette, IN 47907\\
Austria&Austria&U.S.A.\\
\end{tabular}
\footnotetext[1]{$^\dagger$This work was supported by Fonds zur F\"{o}rderung der
Wissenschaftlichen Forschung Project P7497-TEC}
%\footnotetext{This work is supported by Fonds zur F\"{o}rderung der
%Wissenschaftlichen Forschung Project P7497-TEC}
\footnotetext{Support for this research was provided in part by
NSF Grant INT-8912631, CCR-9201078 and NCR-9206315, in part by
AFOSR grant 90-0107, NATO Grant 0057/89,
and grant R01 LM05118 from the National Library of
Medicine.}
\bigskip\bigskip\bigskip
\begin{center}
{\bf Abstract}
\end{center}
\par
\bigskip
Multidimensional digital searching ($M$-d tries) is analyzed
from the view point of partial match retrieval.
Our first result extends the analysis of Flajolet
and Puech of the average cost of retrieval
under the Bernoulli model
to biased probabilities
of symbols occurrences in a key. The second main finding concerns
the variance of the cost of the retrieval in the unbiased case. This
variance is of order $O(N^{1-s/M})$ where $N$ is the number of records stored
in a $M$-d trie, and $s$ is the number of specified components in a query
of size $M$. For $M=2$ and $s=1$ we present a detailed analysis of the
variance, which identifies the constant at $\sqrt{N}$.
This analysis,
which is the central part of our paper, requires certain series
transformation identities which go back to Ramanujan.
In the Appendix we provide a Mellin transform approach to these results.
\end{singlespace}
\vfill
\clearpage
\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}
\big
{\bf 1. INTRODUCTION}
\par
\medskip
Multidimensional searching is
an important algorithmic concept in modern
computer science. In particular, retrieval of multidimensional
data found applications in the design of data base systems and
graphics. Bentley \cite{bentley} and Rivest \cite{rivest} are
founding fathers of multidimensional searching, namely digital
$M$-d trees and $M$-d search trees. An early description of
these structures can be found in volume three of Knuth's book
\cite{knuth}, and a more detailed discussion is
in the book of Mahmoud \cite{mahmoud}.
Several applications of multidimensional searching
are discussed in the paper of Flajolet and Puech \cite{fla-puech},
which also presents a thorough analysis of partial match
retrieval for multidimensional data.
\par
In this paper we concentrate on $M$-d digital trees (i.e.,
M-dimensional tries) and partial match retrieval in such a
data structure.
In general, a {\it trie} stores a set of, say, $N$ items, which
are represented by keys from $\Sigma^\infty$, the set of all
infinite
sequences over a finite alphabet $\Sigma$.
A trie is composed of branching nodes, also called {\it internal nodes}, and
{\it external nodes} that store the keys. In addition, we assume that
every external node is able to store only one key.
The branching policy at any level,
say $k$, is based on the $k$-th symbol of a key. For
example, for a binary alphabet $\Sigma =\{0,1\}$,
if the $k$-th symbol in a key is ``0", then we branch-out left in the trie,
otherwise we go to the right. This process terminates when for the first time
we encounter a different symbol between a key that is currently
inserted into the trie and all other
keys already in the trie. Then, this new key is stored in a newly
generated external node.
In other words, the access path from the root to an external node (a leaf of
a trie) is the minimal
unique prefix of the information contained in this external
node.
(Cf. also
\cite{ahu}, \cite{kps1}, \cite{kps2}, \cite{knuth}, \cite{mahmoud}).
\par
The $M$-d {\it tries} are built in a similar manner, however, this time
a key is an $M$-dimensional tuple.
Let the $i$th key be
$K_i=(K_{i1},\ldots, K_{iM})$, where $K_{ij}\in\Sigma^\infty$,
and $1\leq i\leq N$.
Now we produce for each $1\leq i\leq N$ one sequence $\widetilde{K}_i
\in\Sigma^\infty$ by regular shuffling of the components
$K_{i1},\ldots, K_{iM}$, and use
these new composite keys
$\widetilde{K}_1, \ldots , \widetilde{K}_N$ to construct a regular
trie. More precisely, let $K_i=(K_{i1} ,\ldots, K_{iM})$ and
$K_{i\l}=(k_{i\l}^1, k_{i\l}^2, \dots )$ where $k_{i\l}^m\in \Sigma$
for $1\leq \l \leq M$ and $m\geq 1$. Then, the new $i$th key is
$\widetilde{K}_i=(k_{i1}^1k_{i2}^1\cdots k_{iM}^1 k_{i1}^2 k_{i2}^2 \cdots
k_{iM}^2 \cdots )$. In passing, we note that the statistics of
the composite keys are the same as the original keys provided the
keys are statistically independent.
\par
A {\it partial match query\/} $q=(q_1,\dots,q_M)$,
$q_j\in\Sigma^\infty\cup\{*\}$, asks for all records
$(r_1,\dots,r_M)$ with $r_j=q_j$ for all specified components $q_j$ of the
query.
For example, $q=(S_1,*,S_2)$ asks for all records with (specified)
first component
$S_1$, unspecified second component and (specified)
third component $S_2$.
Because of the construction of the $M$-d tries
it is convenient to transform
a given query $q$ into a one-dimensional {\it search sequence\/}
$\sigma=\sigma(q)\in\left(\Sigma\cup\{*\}\right)^\infty$
by regular shuffling, too.
That is, the first
symbol of $\sigma$ comes from the first symbol of the first component
of $q$ (if the first component is unspecified $*$, then we put $*$ in
$\sigma$ too), the second symbol of $\sigma$ originates from the first symbol
of the second component of $q$, and so on modulo $M$. The search sequence
is used to search for external nodes in an $M$-d trie that satisfy
the pattern, where
``$*$" means to proceed in all directions.
The {\it cost of a query} is defined as the number of internal
nodes visited during such a search.
\par
The cost of a query depends on the search sequence $\sigma$.
In fact, this
sequence specifies a subtree in a trie, and can be considered
as a new parameter that characterizes the trie. For example, if
a query consists only of specified patterns, then the query defines
a specific
path (depth) in the trie. This path may be of various shapes depending
on the search sequence. Indeed, if $\Sigma=\{0,1\}$ and
$\sigma=(1111 \cdots)$,
then the query
finds the right-most internal nodes, and the cost of the query is the
length of such a path; the length of a ``zig-zag" path can be
computed by evaluating the cost of the following search sequence
$\sigma=(0101\cdots)$, etc.
On the other hand, if the query consists of only
unspecified components $*$, then the cost of the query is equivalent
to the size of the underlying trie. Finally, with a mixture of
specified and unspecified components, the cost of a query represents
the size of a subtree of the trie.
In the following, for simplicity of presentation,
we restrict ourselves to the binary alphabet
$\Sigma=\{0,1\}$. We adopt the following
{\it probabilistic model}: Symbols from the alphabet are generated
independently, and 0 and 1 occur with probabilities $p_0$ and $p_1=1-p_0$
respectively ({\it Bernoulli model}).
In \cite{fla-puech} Flajolet and Puech -- using ingenious techniques from complex analysis
and differential equations -- presented a very detailed evaluation
of the {\it expected} cost of a query, assuming equal probabilities
for symbol occurrences. Observe that in this unbiased instance the
expected cost of a fixed query $q$ does not depend on the distribution
of the zeroes and ones in the search sequence $\sigma=\sigma(q)$, but only
on its {\it search pattern} $\w\in\{S,*\}^M$:
If we substitute each specified
element of $\sigma$ by $S$, we obtain a sequence in $\{S,*\}^\infty$
which has period $M$ (since $\sigma$ was constructed by regular
shuffling from $q$), and we denote its prefix of length $M$ by $\w$.
In this paper we extend Flajolet and Puech's result into two directions.
First, we consider the expected cost in the {\it biased case}, that is, when
probabilities of symbol occurrences are not identical. We investigate
two aspects of this problem, namely the
{\it deterministic} instance of {\it fixed
search sequences} $\sigma$ as well as the average cost for random
queries with a {\it fixed search pattern} $\w$, where we assume that the
specified components of the query satisfy the same Bernoulli statistics
as the keys of the trie ({\it nondeterministic instance}).
Our motivation for studying the biased case is mainly to
see the impact of
(e.g. slightly) different probabilities
on the order of the cost. It turns out that this order varies only mildly
if $p_0$ is not too close to either 0 or 1 (compare the table in
Section 2). This result matches well with some other analyses
for biased trie-like structures
by Fayolle, Flajolet and Hofri \cite{ffh}, and
Jacquet \cite{jacquet}.
More importantly, we
also analyze the {\it variance} of the cost
in the unbiased case for $M=2$,
which already requires rather sophisticated mathematical techniques.
We shall show that this variance
is of order $O(\sqrt{N})$, which implies
the convergence {\it in probability} of the cost to its average value.
We also conjecture that for general $M$ the variance is
of order $O(N^{1-s/M})$ where
$s$ is the number of specified components in a query.
We point out that this can be difficult to prove, especially if
one needs to identify the constant at $N^{1-s/M}$.
\par
This paper is organized as follows. In the next section we present
our main results, and discuss some consequences of them. All proofs
are delayed till Section 3. The asymptotic analysis
is based on solving
some recurrences equation through generating function approach,
and obtaining asymptotics of some alternating sums through the
usage of Rice's formula (cf. \cite{fla-sed}) or the
Mellin transform approach (cf. \cite{spa1}). The main difficulty in
this analysis lies in proving that some coefficients in the
asymptotics of the variance are equal to zero.
These kind
of problems were already tackled by us in \cite{kps1} and \cite{kps2}.
However, this time the difficulty is one step higher.
More precisely, during the course of our analysis we require transformation
results for $F(x)=\sum_{k\geq 1} e^{-kx}/(1+e^{-2kx})$ and related functions.
It turns out that by a very general formula of Ramanujan (cf. \cite{berndt})
we have $F(x)=\pi/4x -1/4+\pi F(\pi^2/x)/x$ for $x>0$. In the Appendix
we give an outline of a Mellin transform proof for
this and similar transformation results.
\big
{\bf 2. MAIN RESULTS}
\par
\medskip
In this section we present our main results concerning the expected cost
of a query. We start with the {\it nondeterministic case} of random
queries, with fixed search pattern $\w\in\{S,*\}^M$, where we assume
that the specified components $S$ of the query are generated in the same
manner as the keys stored in the trie, namely 0's and 1's chosen
independently with probabilities $p_0$ resp. $p_1=1-p_0$.
Let $\w^{(k)}$ denote the cyclic shift to the left by $k$ positions of
$\w$. Then
$\w=\w^{(M)}$.
We also write
$\w^\prime=\w^{(1)}$.
Let $H_N^\w(z)$ be the probability generating function of the cost of
a random query with search pattern $\w$. Then the following recurrence
holds for $N\geq 2$:
\begin{equation}
H_N^\w(z)=\left\{\begin{array}{ll}
\med
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} H_k^{\w^{\prime}}(z)
H_{N-k}^{\w^{\prime}}(z) & \w=*\dots \\
\medskip
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k}
\left(p_0H_k^{\w^{\prime}}(z)+p_1H_{n-k}^{\w^{\prime}}(z) \right)&
\w=S\dots
\label{e1a}
\end{array}
\right.
\end{equation}
and $H_0^\w(z)=H_1^\w(z)=1$. (Compare the detailed arguments in
\cite{fla-puech} for the symmetric case.)
The expected cost $l_n^\w$ is the first derivative of $H_N^\w(z)$
at $z=1$. Therefore we have
\begin{equation}
l_N^\w=1+\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k}
\{ \d(0,x_1)l_k^{\w^{\prime}}+\d(1,x_1)l_{N-k}^{\w^{\prime}} \} ~,
\label{e3a}
\end{equation}
$l_0^\w=l_1^\w=0$,
where $\w=(x_1,x_2,\dots,x_M)$ and
\begin{equation}
\d(b,x)=\left\{\begin{array}{ll}
p_b&\mbox{if $x=S$,}\\
1 &\mbox{if $x=*$,}
\end{array}
\right.
\qquad b\in\{0,1\}.
\label{e4a}
\end{equation}
Since $\w=\w^{(M)}$, recurrence (\ref{e3a}) can be solved by iteration,
and the following asymptotic result holds (compare Section 3 for all
details).
\med
{\bf Theorem 1.1}.
{\it Let $\w=(x_1,x_2,\dots,x_M)\in\{S,*\}^M$
and denote by $s_j$ the number of specified components $S$ in
$(x_1,\dots,x_j)$, with $s=s_M$. Then the expected cost
$l_N^\w$ of a random query $q$ with search pattern $\w$ fulfills
for large $N$
{\rm (i)} if $s=M$ (all components specified)
\begin{equation}
l_N^\w= {\log N \over -\left(p_0\log p_0+p_1\log p_1\right)} +O(1) ~,
\label{e4stern}
\end{equation}
{\rm (ii)} if $0~~0$},
\end{equation}
where
$0<\kappa_0<1$ is the unique solution of
\begin{equation}
p_0^{\kappa_0n_0}p_1^{\kappa_0n_1}\left(p_0^{\kappa_0}+p_1^{\kappa_0}
\right)^{n_*}
=1.
\end{equation}
}
The next result is our main finding and it
concerns the variance of the cost in the case where
at least one component of the query is unspecified. This analysis is much
more intricate, as demonstrated in our papers \cite{kps1}, \cite{kps2}
that are devoted to the variance of the external path length in
a trie and PATRICIA respectively. Therefore,
hereafter we assume only the symmetric alphabet, that is,
``0" and ``1" occur
with equal probability $0.5$.
Observe that under this assumption the nondeterministic cost model
coincides with the deterministic one. Now (\ref{e1a}) reads
\begin{equation}
H_N^\w(z)=\left\{\begin{array}{ll}
\med
z\sum_{k=0}^N {N\choose k} 2^{-N} H_k^{\w^{\prime}}(z)
H_{N-k}^{\w^{\prime}}(z) & \w=*\dots\ , \\
\medskip
z\sum_{k=0}^N {N\choose k} 2^{-N} H_k^{\w^{\prime}}(z) &
\w=S\dots \ .
\end{array}
\right. \label{e7}
\end{equation}
\par
If the cost of the query $\w$ is denoted by $C_N^\w$, then the
variance ${\rm var}~C_N^\w$ can be evaluated according to
the following formula
\begin{equation}
{\rm var}~C_N^\w=\left.{d^2 \over dz^2} H_N^\w(z)\right|_{z=1}+
l_N^\w-(l_N^\w)^2,\qquad l_N^\w=E\,C_N^\w ~.
\label{e8}
\end{equation}
\par
The evaluation of the second factorial moment of $C_N^\w$
leads to very tedious algebraic manipulations, although the main idea
behind it is not too complicated.
In the following we restrict our investigations to the case of $M=2$.
As shown in Section 3, the analysis of
the centralized moments in this case is a rather sophisticated one.
\big
{\bf Theorem 2}.
{\it
{\rm (i)} For $\w=(*,S)$ we have asymptotically
\begin{equation}
{\rm var}~C_N^{\w}\sim \sqrt{N} \Big( A_1+ \tau_1(\log_2 \sqrt{N})\Big),
\qquad A_1
\simeq 2.09184~, \label{e9}
\end{equation}
where the constant $A_1$ can be expressed analytically as
\begin{eqnarray}
A_1&=&{7\sqrt{\pi}(1+\sqrt{2})\over 2L}-2\sqrt{\pi}\left(
{1\over L}\left[{73+25\sqrt{2} \over 16\sqrt{2}}-{4\over 3\sqrt{3}}
\right] \right.
\nonumber \\
&+& {2\over L}\sum_{\l\geq 2}{1/2 \choose \l}
{(\l-1)(\l+\half)(1+2^{-\l})
2^{-\l} \over 1-2^{\half -\l}} \Bigg) ~, \label{e10}
\end{eqnarray}
with $L=\log 2$, and $\tau_1(x)$ is a continuous periodic function of period
1, mean 0 and $|\tau_1(x)|<5\cdot 10^{-3}$.
\parsec
For $\w=(S,*)$ we have
\begin{equation}
{\rm var}~C_N^{\w}\sim \sqrt{N}\Big({A_1\over \sqrt 2}
+ \tau_2(\log_2 \sqrt{N}) \Big),\qquad {A_1\over \sqrt 2}
\simeq 1.47916~, \label{e11}
\end{equation}
where
$\tau_2(x)$ is again of period 1, mean 0 and $|\tau_2(x)|<5\cdot 10^{-3}$.
\med
{\rm (ii)} The cost of the query $\w$ converges in probability to
$EC_N^\w=\l_N^\w$, that is, the following holds
\begin{equation}
\lim_{N \con \infty} \pr\{\mid C_N^\w/l_N^\w -1\mid > \eps \}=0
\label{e13}
\end{equation}
for any $\eps>0$.}
\med
{\bf Remarks}.
\med
(i) {\it Periodic Fluctuations}. The Fourier coefficients of $\tau_1$
and $\tau_2$ can be computed too, but we omit them here since the expressions
are rather complicated.
Estimating these coefficients we obtain the upper bounds for the
amplitudes.
\med
(ii) {\it Proof of Theorem 2(ii)}. We just note that part (ii) of
Theorem 2 follows directly from part (i) and Chebyshev's inequality.
\med
(iii) {\it Extensions}. Our results can be extended in many
directions. For example, it is easy to see that they hold for
$V$-ary symmetric tries, that is, when $\Sigma=\{1,2, \cdots , V\}$.
It may be interesting to extend our Theorem 2 to an asymmetric alphabet,
and it is even more challenging to assume some dependency among
symbols in the alphabet $\Sigma$. Finally, one may replace the
regular tries by other digital structures such as Patricia tries and
digital search trees. Some preliminary results in this direction
are reported in \cite{kp}.
Also, a rigorous analysis of suffix trees with partial match retrieval
might be of some interest.
\big
{\bf 3. ANALYSIS}
\par
\medskip
In this section we prove Theorems 1.1, 1.2 and 2.
\med
{\bf 3.1 The Expected Cost in the Asymmetric Case}
\par
\medskip
Let us consider the nondeterministic case at first.
We start our analysis from the
recurrence equation (\ref{e3a}) for the average cost $l_N^\w$ of
a random query with search pattern $\w=(x_1,\dots,x_M)\in\{S,*\}^M$.
Let $L^\w(z)$ be the
exponential generating function of the cost, that is,
$L^\w(z)=\sum_{N=0}^\infty l_N^\w z^N/N!~$. Then recurrence (\ref{e3a})
can be transformed into the following functional equation
$$L^\w(z)=\d(0,x_1)L^{\w^{\prime}}(zp_0)e^{p_{1}z}
+\d(1,x_1)L^{\w^{\prime}}(zp_1)e^{p_{0}z} +b(z) ~,$$
where $b(z)=e^z-1-z$. Introducing the transform $\t{L}^\w(z)=e^{-z}L^\w(z)$
we reduce the above to
$$
\t{L}^\w(z)=\d(0,x_1)\t{L}^{\w^{\prime}}(zp_0)+
\d(1,x_1)\t{L}^{\w^{\prime}}(zp_1) +\t{b}(z) ~,
$$
with $\t{b}(z)=e^{-z}b(z)$. Using the fact that $\w=\w^{(M)}$,
we obtain after $M$ iterations
\begin{eqnarray}
\t{L}^\w(z)&=&\sum_{\b\in\Theta_{M}} \d(b_1,x_1) \cdots \d(b_M,x_M)\,
\t{L}^\w(zp_{b_{1}} \cdots p_{b_{M}}) \nonumber\\
&+&\sum_{j=0}^{M-1}
\sum_{\b\in\Theta_{j}} \d(b_1,x_1) \cdots \d(b_j,x_j)\, \t{b}(zp_{b_{1}}
\cdots p_{b_{j}}) ~,\label{e1mond}
\end{eqnarray}
where $\Theta_j=\{0,1\}^j$.
This functional equation is easy to solve. Comparing the coefficients
of $\t{L}^\w(z)$ at $z^N/N!$ we get
\begin{equation}
\t{l}_N^\w={(-1)^N (N-1)\sum_{j=0}^{M-1} \sum_{\b\in\Theta_{j}}
\prod_{i=1}^j
\d(b_i,x_i)p_{b_{i}}^N \over 1-\sum_{\b\in\Theta_{M}} \prod_{i=1}^M
\d(b_i,x_i) p_{b_{i}}^N } ~.
\nonumber
\end{equation}
From the definition of $\delta(b_i,x_i)$ it follows that
$$
\sum_{\b\in\Theta_{j}}\prod_{i=1}^j
\d(b_i,x_i) p_{b_{i}}^N =
\left(p_0^{1+N}+p_1^{1+N}\right)^{s_j}\left(p_0^N+p_1^N\right)
^{j-s_j}=:P(N;s_j)
$$
where $s_j$ is the number of components $S$ among $(x_1,\dots,x_j)$.
Therefore, with $s=s_M$,
\begin{equation}
\t{l}_N^\w={(-1)^N (N-1)\sum_{j=0}^{M-1} P(N;s_j)
\over 1-
P(N;s)},\qquad N\ge 1
~.
\label{e15}
\end{equation}
To recover the original average cost $l_N^\w$ we note that
$l_N^\w=\sum_{k=1}^N {N \choose k}
\t{l}_k^\w$.
\par
The asymptotics of $l_N^\w$ can now be obtained by a
Mellin transform approach (cf. \cite{spa1})
or
Rice's formula (compare Section 3.2).
In particular, using \cite{spa1} we translate $l_N^\w$ into
the following Mellin-like integral
$$
l_N^\w = {1\over 2\pi i} \int_{-3/2-i \infty}^{-3/2+i \infty}
{\Gamma(z) N^{-z} (z+1)\sum_{j=0}^{M-1}
P(-z;s_j)
\over 1-
P(-z;s)
} dz \cdot\left(1+O({1\over N})\right) ~.$$
Shifting the contour of integration to the right and
computing the residues of the integrand we finally
obtain Theorem 1.1. Note that in the case
$s=M$ there is a double
pole at $z=0$ which produces the logarithm function in Theorem 1.1(i).
In the case $0~~~~0$ such that $\alpha \beta=\pi$ and
$y \in {\rm I\! R} $ with $|y|<\beta/2$ the following holds}
\begin{equation}
\alpha\left\{{1\over 4}\sec (\alpha y) +\sum_{k=1}^\infty
\chi(k){\cos (\alpha y k) \over e^{k\alpha^{2}}-1}\right\} =
\beta\left\{ {1\over 4} +\half \sum_{k=1}^\infty
{\cosh (2\beta y k) \over \cosh (k \beta^{2})} \right\} ~.
\label{e32a}
\end{equation}
\med
For $y=0$ this reads
$$
\alpha\left\{{1\over 4} +\sum_{k=1}^\infty
\chi(k){1 \over e^{k\alpha^{2}}-1}\right\} =
\beta\left\{ {1\over 4} +\half \sum_{k=1}^\infty
{1 \over \cosh (k \beta^{2})} \right\} ~.
$$
Replacing in the above $\cosh(x)$ by the exponential functions, expanding
the geometric series and rearranging the sums we obtain
$$
\half \sum_{k\geq 1}{1\over \cosh(k \beta^2)} = \sum_{j\geq 1}
\chi(j) {1\over e^{j\beta^{2}}-1} ~,
$$
so that, taking into account the constraint $\alpha \beta=\pi$, we find
$$
\alpha \left({1\over 4}+F(\alpha^2)\right)=
\beta\left({1\over 4}+F(\beta^2)\right) ~.
$$
Now, we substitute in the above $\alpha=\sqrt{x}$ and
$\beta=\pi /\sqrt{x}$. Then,
\begin{equation}
F(x)={\pi \over 4x}-{1\over 4}+{\pi \over x}F\left({\pi^2\over x}\right)
\label{e33a}
\end{equation}
for $x>0$, which is the desired transformation result.
For $G(x)$ we observe that
$G(x)=F(x)-2F(2x)$, hence
\begin{equation}
G(x)={1\over 4}+{\pi \over x}F\left({\pi^2\over x}\right)-
{\pi \over x}F\left({\pi^2 \over 2x}\right) ~.
\label{e34a}
\end{equation}
Applying the above to (\ref{e34}) we finally obtain
\begin{equation}
[(\tau^\w)^2]_0
=\frac{3}{4L}-\frac{\pi}{4L^2}\left(3+2\sqrt 2\right)
+\frac{3-2\sqrt 2}{L}F(L)
+\frac{2\sqrt 2}{L}F\left(\frac L2\right) ~. \label{e35}
\end{equation}
Using (\ref{e35}) $B=0$ follows by some obvious simplifications.
Thus, we have
proved
${\rm var}~C_N^\w=O(\sqrt{N})$.
The coefficient $A_1$ at $\sqrt{N}$ in (\ref{e29}) is given in Theorem
2(i) equation (\ref{e10}).
\par
The second pattern $\w=(S,*)$ can be analyzed in a similar manner as above.
We finally mention, that it is not at all obvious how to
extend this result to the case $M\geq 3$. The reader
should note that the key arguments in our proof of Theorem 2(i)
are the transformations result (\ref{e33a}) and (\ref{e34a}).
For $M\geq 3$ there is
no
comparable result in {\it Ramanujan's Notebooks}, and the alternative
proof presented in the Appendix relies heavily on the duplication
formula
for the gamma function, which is not suitable for $M\geq 3$.
\begin{comment}
Finally, proof of Theorem 2(i) follows the same path as above.
Algebra involved is very tedious, but the final result
(without explicit constant) is simple. In fact, intuitively
one must expect this kind of behavior, since the size of a
trie -- which dominates cost of all other partial match retrieval --
has the variance of $O(N)$, as shown in \cite{rj}.
\end{comment}
\big
{\bf APPENDIX: Mellin Transform Approach to Ramanujan-Like Series
Identities}
\par
\medskip
Most proofs of results like
Ramanujan's formula (\ref{e32a}) resp.
(\ref{e33}) use the
theory of {\it modular functions} (cf. \cite{berndt}). In this appendix
we outline the alternative approach using {\it Mellin integrals},
a line of attack, suggested to us by P. Flajolet, that belongs to the
toolkit of analytic number theory (cf. \cite{apo2}).
\par
To prove (\ref{e33a}) we proceed as follows. Let
$$
\beta(s)=\sum_{j\geq 0} (-1)^j {1\over (2j+1)^s} ~.
$$
Using definition (\ref{e33}) of $F(x)$, we have
$$
F(x)=\sum_{k\geq 1}{e^{-kx}\over 1+e^{-2kx}}=
\sum_{j\geq 0} (-1)^j \sum_{k\geq 1}e^{-k(2j+1)x} ~,
$$
so that the Mellin transform
$F^*(s)=\int_0^\infty F(x) x^{s-1} dx$ of $F(x)$ (cf. \cite{davis})
becomes
$$F^*(s)=\Gamma(s)\zeta(s)\beta(s) ~,$$
where $\zeta(s)$ is Riemann's zeta function \cite{abramowitz}.
By the Mellin inversion formula this yields
\begin{equation}
F(x)={1\over 2\pi i} \int_{3/2-i \infty}^{3/2+i \infty} \Gamma(s)\zeta(s)
\beta(s) x^{-s} ds ~.
\label{e38}
\end{equation}
Now we take the two residues $s=1$ and $s=0$
out from the above integral
(observe that $\beta(0)=1/2$ and $\beta(1)=\pi/4$
(cf. \cite{abramowitz}) and apply the
the duplication formula for $\Gamma(s)$
to obtain
$$
F(x)=
\frac{\pi}{4x}-\frac 14+
\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}^{-\frac 12+i\infty}
\frac{1}{\sqrt\pi}2^{s-1}\Gamma\left(\frac s2\right)\Gamma
\left(\frac {s+1}2\right)
x^{-s}\zeta(s)\beta(s)ds~.
$$
(Observe that the exponential smallness of the $\Gamma$-function along
vertical lines justifies the shifting of the line integral.)
We now use the functional equations
for $\zeta(s)$ and $\beta(s)$, namely
\begin{equation}
\Gamma\left(\frac s2\right)\zeta(s)=\pi^{s-\frac 12}
\Gamma\left(\frac {1-s}2\right)\zeta(1-s)
\label{e39}
\end{equation}
and
\begin{equation}
\beta(1-s)\Gamma\left(1-\frac s2\right)=
2^{2s-1}\pi^{-s+\frac 12}\Gamma\left(\frac{s+1}{2}\right)\beta(s) ~.
\label{e40}
\end{equation}
Identity (\ref{e39}) is Riemann's functional equation for
$\zeta(s)$, and (\ref{e40}) is an immediate consequence of
the functional equation for Hurwitz's $\zeta$-function
$\zeta(s,a)$ (cf. \cite{apostol}), and the fact that
$$
\beta(s)=4^{-s}\left[\zeta(s,{1\over 4})-\zeta(s, {3\over 4})\right] ~.
$$
Using (\ref{e39}) and (\ref{e40}), and substituting $1-s=u$, we get
$$
F(x)=
\frac{\pi}{4x}-\frac 14+
\frac{1}{2\pi i}\int\limits_{\frac 32-i\infty}^{\frac 32+i\infty}
\pi^{1-2u}\Gamma(u)x^{u-1}\zeta(u)\beta(u)du ~.
$$
This proves (\ref{e33a}).
\par
\medskip
Using the above scheme {\it several other identities} can be proved.
Below we just list some of them. Define
\begin{eqnarray}
f(x)&=&\sum_{k\ge1}\frac{e^{kx}}{\left(e^{kx}-1\right)^2}=
\sum_{k\ge1}\frac{k}{e^{kx}-1}, \\
g(x)&=&\sum_{k\ge1}\frac{(-1)^{k-1}}{k\left(e^{kx}-1\right)}, \\
h(x)&=&\sum_{k\ge1}\frac{1}{k\left(e^{2k\pi x}-1\right)} ~.
\end{eqnarray}
Then, the following identities hold:
\begin{enumerate}
\item
$$
1+2\sum_{n\ge1}e^{-\pi n^2x}=\frac{1}{\sqrt x}+\frac{2}{\sqrt x}
\sum_{n\ge1}e^{-\pi n^2/x} \ \ \ \ \ \ \ \ \mbox{Jacobi's $\vartheta$--function},
$$
\item
$$
f(x)=\frac{1}{x^2}\frac{\pi^2}{6}-\frac{1}{2x}+\frac{1}{24}
-\frac{4\pi^2}{x^2}f\left(\frac{4\pi^2}{x}\right) \ \ \
\mbox{Ramanujan \cite{berndt}},
$$
\item
$$
g(x)=\frac{\pi^2}{12x}-\frac{\log 2}{2}+\frac{x}{24}-
g\left(\frac{2\pi^2}{x}\right) \ \ \ \ \ \ \ \
\mbox{Ramanujan \cite{berndt}},
$$
\item
$$
\ \ \ \ \ \ h(x)=\frac{\pi }{12}\left(\frac 1x-x\right)+\frac{\log x}{2}+
h\left(\frac{1}{x}\right) \ \ \ \
\mbox{Dedekind and Ramanujan \cite{berndt}}.
$$
\end{enumerate}
The latter three identities play a prominent role in the analysis of
the variance for some parameters of tries (cf. \cite{kp1}, \cite{kps1},
\cite{kps2}).
\med
{\bf Remark}. It is fairly well known that the functional equations
for the Riemann $\zeta$-function and the
$\vartheta$-function can be derived from each other via the
Mellin transform (see e.g., \cite{bellman}, \cite{borwein}).
Here we would like to point out the analogous $\vartheta$-like
identity that is related to the functional equation for $\beta(s)$.
Let
$$
H(x)=\sum_{j\geq 0} (-1)^j (2j+1)e^{-(2j+1)^{2}x} ~,
\qquad
\mbox{then}\qquad
H(x)={1\over 8}\left({\pi \over x}\right)^{3/2}H\left({\pi^2 \over 16x}
\right) ~.
$$
\med
{\bf ACKNOWLEDGMENTS}
\par
\medskip
We would like to thank Philippe Flajolet, INRIA, for
his long standing support of our work, and several fruitful discussions
on the subject of this paper, as well as the anonymous referees for
several helpful remarks.
\begin{singlespace2}
\begin{thebibliography}{99}
\bibitem{abramowitz}
M. Abramowitz and I.A. Stegun,
{\it Handbook of Mathematical Functions},
Dover, New York 1970.
\bibitem{ahu}
A.V. Aho, J.E. Hopcroft and J.D. Ullman,
{\it
The Design and Analysis of Computer Algorithms,
}
Addison-Wesley, Reading Mass. 1974.
\bibitem{apostol}
T. Apostol,
{\it Introduction to Analytical Number Theory},
Springer-Verlag, New York 1976.
\bibitem{apo2}
T. Apostol,
{\it Modular Functions and Dirichlet Series in Number Theory},
Springer-Verlag, New York 1978.
%\bibitem{axa}
%A. Apostolico,
%The Myriad Virtues of Suffix Trees,
%{\it
%Combinatorial Algorithms on Words,
%}
%pp. 85--96, Springer-Verlag, ASI F12 (1985).
%\bibitem{axa-spa}
%A. Apostolico and W. Szpankowski,
%Self-Alignments in Words and Their Applications,
%{\it J. Algorithms}, 13, 446--467, 1992.
\bibitem{bellman}
R. Bellman,
{\it Analytic Number Theory -- An Introduction},
Benjamin-Cummings, London 1980.
\bibitem{bentley}
J. L. Bentley,
Multidimensional Binary Search Trees Used for Associative Searching,
{\it Communication of the ACM}, 18, 509-517, 1975.
\bibitem{berndt}
B.C. Berndt,
{\it Ramanujan's Notebooks. Part II},
Springer-Verlag, New York 1989.
\bibitem{borwein}
J. Borwein and P. Borwein,
{\it Pi and the AGM},
John Wiley \& Sons, New York 1987.
\bibitem{davis}
B. Davis,
{\it Integral Transforms and Their Applications},
Springer-Verlag, New York 1978.
%\bibitem{dsr}
%L. Devroye, W. Szpankowski and B. Rais,
%A Note on the Height of Suffix Trees,
%{\it SIAM J. Computing}, 21, 48-53, 1992.
%\bibitem{erdos}
%P. Erd\"{o}s and P. R\'{e}v\'{e}sz,
%On the Length of the Longest Run of Heads,
%{\it Colloquia Math. Soc. J. Bolyai}, 16, 219-228, 1975.
\bibitem{ffh}
G.Fayolle, P.Flajolet and M.Hofri, On a functional equation arising
in the analysis of a protocol for a multiaccess broadcast channel,
{\it Advances in Applied Probability}, 18, 1986, 441--472.
\bibitem{fla-puech}
P. Flajolet and C. Puech,
Partial Match Retrieval of Multidimensional Data,
{\it J. of the ACM}, 33, 371-407, 1986.
\bibitem{fla-sed}
P. Flajolet and R. Sedgewick,
Digital Search Trees Revisited,
{\it SIAM J. Computing}, 15, 748-767, 1986.
%\bibitem{gordon}
%L. Gordon, M. Schilling and M. Waterman,
%An Extreme Value Theory for Long Head Runs,
%{\it Probab. Theory and Related Topics}, 72, 279-287, 1986.
%\bibitem{go}
%L. Guibas and A.M. Odlyzko,
%A Long Repetitive Patterns in Random Sequences,
%{\it Z. Wahrscheinlichkeitstheorie verw. Gebiete}, 38, 241-262, 1980.
\bibitem{henrici}
P. Henrici,
{\it Applied and Computational Complex Analysis},
John Wiley\&Sons, New York 1977.
\bibitem{jacquet}
P. Jacquet,
{\it Contribution de l'Analyse d'Algorithmes \`a l'\'Evaluation
des Protocoles de Communications},
Th\`ese, Universit\'e de Paris Sud-Orsay, 1989.
%\bibitem{js}
%P. Jacquet and W. Szpankowski,
%Autocorrelation on Words and Its Applications, \\
%{\it J. Combinatorial Theory, Ser. A},
%to appear.
\bibitem{kp1}
P. Kirschenhofer and H. Prodinger,
On Some Applications of Formulae of Ramanujan in the Analysis of
Algorithms,
{\it Mathematika}, 38, 14-33, 1991.
\bibitem{kp}
P. Kirschenhofer and H. Prodinger,
Multidimensional Digital Searching -- Alternative Data Structures,
{\it Proc. Random Graphs'91}, John Wiley \& Sons, 1992.
\bibitem{kps1}
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the Variance of the External Path length in a Symmetric Digital Tries,
{\it Discrete Applied Mathematics}, 25, 129-143, 1989.
\bibitem{kps2}
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the balance Property of Patricia Tries: External Path Length Viewpoint,
{\it Theoretical Computer Science}, 68, 1-17, 1989.
\bibitem{knuth}
D.E. Knuth,
{\it The Art of Computer Programming. Vol. 3},
Addison-Wesley, Reading MA 1973.
\bibitem{mahmoud}
H. Mahmoud,
{\it Evolution of Random Search Trees},
John Wiley \& Sons, New York, 1992.
\bibitem{rj}
M. R\'{e}gnier and P. Jacquet,
New Results on the Size of Tries,
{\it IEEE Trans. Information Theory},
35, 203-205 (1989).
\bibitem{rivest}
R. L. Rivest,
Partial-Match Retrieval Algorithm,
{\it SIAM J. Computing}, 5, 19-50, 1976.
\bibitem{spa1}
W. Szpankowski,
The Evaluation of an Alternating Sum with Applications to the
Analysis of Some Data Structures,
{\it Information Processing Letters}, 28, 13-19, 1988.
\end{thebibliography}
\end{singlespace2}
\end{document}
~~