\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 $00$}, \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 $00$ 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}