MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW

PARAMETERS IN TRIES

April 26, 1996

Peter Kirschenhofer^{∗}  Helmut Prodinger^{†}  Wojciech Szpankowski^{‡}
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.

Abstract

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.

∗^{†}This work was supported by Fonds zur Förderung der Wissenschaftlichen Forschung Project P7497-TEC

‡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.

1. INTRODUCTION

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 [6] and Rivest [22] 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 [19], and a more detailed discussion is in the book of Mahmoud [20]. Several applications of multidimensional searching are discussed in the paper of Flajolet and Puech [11], which also presents a thorough analysis of partial match retrieval for multidimensional data.

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 trie stores a set of, say, N items, which are represented by keys from Σ^{∞}, the set of all infinite sequences over a finite alphabet Σ. A trie is composed of branching nodes, also called internal nodes, and 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 Σ = {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 [2], [17], [18], [19], [20]).

The M-d tries are built in a similar manner, however, this time a key is an Mdimensional tuple. Let the ith key be K_{i} = (K_{i1}, …, K_{iM}), where K_{ij} ∈ Σ^{∞}, and 1 ≤ i ≤ N. Now we produce for each 1 ≤ i ≤ N one sequence K̃_{i} ∈ Σ^{∞} by regular shuffling of the components K_{i1}, …, K_{iM}, and use these new composite keys K̃_{1}, …, K̃_{N} to construct a regular trie. More precisely, let K_{i} = (K_{i1}, …, K_{iM}) and K_{iℓ} = (k_{iℓ}^{1}, k_{iℓ}^{2}, …) where k_{iℓ}^{m} ∈ Σ for 1 ≤ ℓ ≤ M and m ≥ 1. Then, the new ith key is K̃_{i} = (k_{i1}^{1}k_{i2}^{1} ⋯ k_{iM}^{1}k_{i1}^{2}k_{i2}^{2} ⋯ k_{iM}^{2} ⋯). In passing, we note that the statistics of the composite keys are the same as the original keys provided the keys are statistically independent.

A partial match query q = (q_{1}, …, q_{M}), q_{j} ∈ Σ^{∞} ∪ {∗}, asks for all records (r_{1}, …, 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 search sequence σ = σ(q) ∈ (Σ ∪ {∗})^{∞} by regular shuffling, too. That is, the first symbol of σ comes from the first symbol of the first component of q (if the first component is unspecified ∗, then we put ∗ in σ too), the second symbol of σ 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 cost of a query is defined as the number of internal nodes visited during such a search.

The cost of a query depends on the search sequence σ. 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 Σ = {0, 1} and σ = (1111 ⋯), 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 σ = (0101 ⋯), 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 Σ = {0, 1}. We adopt the following 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 (Bernoulli model). In [11] Flajolet and Puech – using ingenious techniques from complex analysis and differential equations – presented a very detailed evaluation of the 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 σ = σ(q), but only on its search pattern ω ∈ {S, ∗}^{M}: If we substitute each specified element of σ by S, we obtain a sequence in {S, ∗}^{∞} which has period M (since σ was constructed by regular shuffling from q), and we denote its prefix of length M by ω.

In this paper we extend Flajolet and Puech’s result into two directions. First, we consider the expected cost in the biased case, that is, when probabilities of symbol occurrences are not identical. We investigate two aspects of this problem, namely the deterministic instance of fixed search sequences σ as well as the average cost for random queries with a fixed search pattern ω, where we assume that the specified components of the query satisfy the same Bernoulli statistics as the keys of the trie (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 [10], and Jacquet [14].

More importantly, we also analyze the 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 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}.

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. [12]) or the Mellin transform approach (cf. [23]). 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 [17] and [18]. However, this time the difficulty is one step higher. More precisely, during the course of our analysis we require transformation results for F (x) = ∑_{k≥1} e^{−kx}/(1 + e^{−2kx}) and related functions. It turns out that by a very general formula of Ramanujan (cf. [7]) we have F (x) = π/4x − 1/4 + πF (π^{2}/x)/x for x > 0. In the Appendix we give an outline of a Mellin transform proof for this and similar transformation results.

2. MAIN RESULTS

In this section we present our main results concerning the expected cost of a query. We start with the nondeterministic case of random queries, with fixed search pattern ω ∈ {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 ω^{(k)} denote the cyclic shift to the left by k positions of ω. Then ω = ω^{(M)}. We also write ω′ = ω^{(1)}. Let H_{N}^{ω}(z) be the probability generating function of the cost of a random query with search pattern ω. Then the following recurrence holds for N ≥ 2:

H_{N}^{ω}(z) = \{ \begin{matrix}z ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}H_{k}^{ω′}(z)H_{N−k}^{ω′}(z) & ω = ∗ … \\ z ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k} (p_{0}H_{k}^{ω′}(z) + p_{1}H_{n−k}^{ω′}(z)) & ω = S … \end{matrix}  (1)

and H_{0}^{ω}(z) = H_{1}^{ω}(z) = 1. (Compare the detailed arguments in [11] for the symmetric case.)

The expected cost l_{n}^{ω} is the first derivative of H_{N}^{ω}(z) at z = 1. Therefore we have

l_{N}^{ω} = 1 + ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}\{δ(0, x_{1})l_{k}^{ω′} + δ(1, x_{1})l_{N−k}^{ω′}\} ,  (2)

l_{0}^{ω} = l_{1}^{ω} = 0, where ω = (x_{1}, x_{2}, …, x_{M}) and

δ(b, x) = \{ \begin{matrix}p_{b} & if x = S, \\ 1 & if x = ∗, \end{matrix}  b ∈ \{0, 1\}.  (3)

Since ω = ω^{(M)}, recurrence (2) can be solved by iteration, and the following asymptotic result holds (compare Section 3 for all details).

Theorem 1.1. Let ω = (x_{1}, x_{2}, …, x_{M}) ∈ {S, ∗}^{M} and denote by s_{j} the number of specified components S in (x_{1}, …, x_{j}), with s = s_{M}. Then the expected cost l_{N}^{ω} of a random query q with search pattern ω fulfills for large N (i) if s = M (all components specified)

l_{N}^{ω} = \frac{log N}{− (p_{0} log p_{0} + p_{1} log p_{1})} + O(1) ,  (4)

(ii) if 0 < s < M

l_{N}^{ω} ∼ N^{κ_{0}} (\frac{Γ(−κ_{0})(1 − κ_{0}) ∑_{j=0}^{M−1} (p_{0}^{1+κ_{0}} + p_{1}^{1+κ_{0}})^{s_{j}} (p_{0}^{κ_{0}} + p_{1}^{κ_{0}})^{j−s_{j}}}{s\frac{p_{0}^{1+κ_{0}} log p_{0}+p_{1}^{1+κ_{0}} log p_{1}}{p_{0}^{1+κ_{0}}+p_{1}^{1+κ_{0}}} + (M − s)\frac{p_{0}^{κ_{0}} log p_{0}+p_{1}^{κ_{0}} log p_{1}}{p_{0}^{κ_{0}}+p_{1}^{κ_{0}}}} + ξ(N)) (5)

where 0 < κ_{0} < 1 is the unique real solution of the equation

(p_{0}^{1+κ_{0}} + p_{1}^{1+κ_{0}})^{s} (p_{0}^{κ_{0}} + p_{1}^{κ_{0}})^{M−s} = 1,  (6)

and ξ(N) is an oscillating function which is zero if \frac{log p_{0}}{log p_{1}} is irrational.

Observe that for s = M l_{N}^{ω} is the same as the average depth of a randomly selected external node ([19], [20]). The denominator h = −p_{0} log p_{0} − p_{1} log p_{1} is the entropy.

For the reader’s convenience we present a table of exponents κ_{0} = κ_{0}(p_{0}, \frac{s}{M}):

\begin{matrix}p\\frac{s}{M} & \frac{1}{4} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{3}{4} \\ \frac{1}{10} & 0.838 & 0.779 & 0.648 & 0.492 & 0.398 \\ \frac{1}{5} & 0.799 & 0.727 & 0.574 & 0.405 & 0.314 \\ \frac{1}{4} & 0.784 & 0.708 & 0.549 & 0.380 & 0.290 \\ \frac{1}{3} & 0.765 & 0.685 & 0.521 & 0.352 & 0.266 \\ \frac{1}{2} & 0.750 & 0.667 & 0.500 & 0.333 & 0.250 \end{matrix}

We note that the exponent κ_{0} varies substantially with s/M, while the variation of κ_{0} with respect to p is rather small.

In the deterministic case we ask for the expected cost of a fixed query q with associated query sequence σ = (x_{1}, x_{2}, …) ∈ {0, 1, ∗}^{∞}. This time we have the following equations for the probability generating functions

H_{N}^{σ}(z) = \{ \begin{matrix}z ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}H_{k}^{σ′}(z)H_{N−k}^{σ′}(z) & σ = ∗σ′ \\ z ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}H_{k}^{σ′}(z) & σ = 0σ′ \\ z ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}H_{N−k}^{σ′}(z) & σ = 1σ′ , \end{matrix}  (7)

and for the expected cost

l_{N}^{σ} = 1 + ∑_{k=0}^{N} \binom{N}{k}p_{0}^{k}p_{1}^{N−k}\{ε(0, x_{1})l_{k}^{σ′} + ε(1, x_{1})l_{N−k}^{σ′}\} ,  (8)

where σ = (x_{1}, x_{2}, …) and, for b ∈ {0, 1}, x ∈ {0, 1, ∗}

ε_{b,x} = \{ \begin{matrix}1 & if x = ∗ \\ 1 & if x ∈ \{0, 1\}, b = x \\ 0 & if x ∈ \{0, 1\}, b ≠ x . \end{matrix}  (9)

In general, (8) can be solved by iteration, but the asymptotic behavior of the solution will depend heavily on the structure of the 0,1–pattern of σ (observe that the ∗–pattern has period M). In the case where σ is periodic with period k similar analytic techniques as in the nondeterministic case can be applied. Since the structure of the result is quite similar to Theorem 1.1., we only give the exponent of N in case (ii).

Theorem 1.2. Let σ ∈ {0, 1, ∗}^{∞} be a fixed search sequence of period k with n_{a} symbols a ∈ {0, 1, ∗} per period. Then, for large N,

(i)

l_{N}^{σ} ∼ \frac{k log N}{−n_{0} log p_{0} − n_{1} log p_{1}} + O(1),  if n_{∗} = 0, and  (10)

(ii)

l_{N}^{σ} ∼ N^{κ_{0}} · (C(σ, p_{0}) + ξ_{1}(N)) ,  if n_{∗} > 0,  (11)

where 0 < κ_{0} < 1 is the unique solution of

p_{0}^{κ_{0}n_{0}}p_{1}^{κ_{0}n_{1}} (p_{0}^{κ_{0}} + p_{1}^{κ_{0}})^{n_{∗}} = 1.  (12)

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 [17], [18] 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 (1) reads

H_{N}^{ω}(z) = \{ \begin{matrix}z ∑_{k=0}^{N} \binom{N}{k}2^{−N}H_{k}^{ω′}(z)H_{N−k}^{ω′}(z) & ω = ∗ …, \\ z ∑_{k=0}^{N} \binom{N}{k}2^{−N}H_{k}^{ω′}(z) & ω = S …. \end{matrix}  (13)

If the cost of the query ω is denoted by C_{N}^{ω}, then the variance var C_{N}^{ω} can be evaluated according to the following formula

var C_{N}^{ω} = \frac{d^{2}}{dz^{2}} H_{N}^{ω}(z)|_{z=1} + l_{N}^{ω} − (l_{N}^{ω})^{2},  l_{N}^{ω} = E C_{N}^{ω} .  (14)

The evaluation of the second factorial moment of C_{N}^{ω} 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.

Theorem 2. (i) For ω = (∗, S) we have asymptotically

var C_{N}^{ω} ∼ \sqrt{N}(A_{1} + τ_{1}(log_{2} \sqrt{N})),  A_{1} ≃ 2.09184 ,  (15)

where the constant A_{1} can be expressed analytically as

A_{1} = \frac{7\sqrt{π}(1 + \sqrt{2})}{2L} − 2\sqrt{π} (\frac{1}{L} [\frac{73 + 25\sqrt{2}}{16\sqrt{2}} − \frac{4}{3\sqrt{3}}]
+ \frac{2}{L} ∑_{ℓ≥2} \binom{1/2}{ℓ}\frac{(ℓ − 1)(ℓ + \frac{1}{2})(1 + 2^{−ℓ})2^{−ℓ}}{1 − 2^{\frac{1}{2} −ℓ}} ) ,  (16)

with L = log 2, and τ_{1}(x) is a continuous periodic function of period 1, mean 0 and |τ_{1}(x)| < 5 · 10^{−3}. For ω = (S, ∗) we have

var C_{N}^{ω} ∼ \sqrt{N}(\frac{A_{1}}{\sqrt{2}} + τ_{2}(log_{2} \sqrt{N})),  \frac{A_{1}}{\sqrt{2}} ≃ 1.47916 ,  (17)

where τ_{2}(x) is again of period 1, mean 0 and |τ_{2}(x)| < 5 · 10^{−3}.

(ii) The cost of the query ω converges in probability to EC_{N}^{ω} = ℓ_{N}^{ω}, that is, the following holds

lim_{N→∞} Pr{| C_{N}^{ω}/l_{N}^{ω} − 1 |> ε} = 0  (18)

for any ε > 0.

Remarks.

(i) Periodic Fluctuations. The Fourier coefficients of τ_{1} and τ_{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.

(ii) Proof of Theorem 2(ii). We just note that part (ii) of Theorem 2 follows directly from part (i) and Chebyshev’s inequality.

(iii) 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 Σ = {1, 2, ⋯, 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 Σ. 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 [16]. Also, a rigorous analysis of suffix trees with partial match retrieval might be of some interest.

3. ANALYSIS

In this section we prove Theorems 1.1, 1.2 and 2.

3.1 The Expected Cost in the Asymmetric Case

Let us consider the nondeterministic case at first.

We start our analysis from the recurrence equation (2) for the average cost l_{N}^{ω} of a random query with search pattern ω = (x_{1}, …, x_{M}) ∈ {S, ∗}^{M}. Let L^{ω}(z) be the exponential generating function of the cost, that is, L^{ω}(z) = ∑_{N=0}^{∞} l_{N}^{ω}z^{N}/N! . Then recurrence (2) can be transformed into the following functional equation

L^{ω}(z) = δ(0, x_{1})L^{ω′}(zp_{0})e^{p_{1}z} + δ(1, x_{1})L^{ω′}(zp_{1})e^{p_{0}z} + b(z) ,

where b(z) = e^{z} − 1 − z. Introducing the transform L̃^{ω}(z) = e^{−z}L^{ω}(z) we reduce the above to

L̃^{ω}(z) = δ(0, x_{1})L̃^{ω′}(zp_{0}) + δ(1, x_{1})L̃^{ω′}(zp_{1}) + b̃(z) ,

with b̃(z) = e^{−z}b(z). Using the fact that ω = ω^{(M)}, we obtain after M iterations

L̃^{ω}(z) = ∑_{b∈Θ_{M}} δ(b_{1}, x_{1}) ⋯ δ(b_{M}, x_{M}) L̃^{ω}(zp_{b_{1}} ⋯ p_{b_{M}})
+ ∑_{j=0}^{M−1} ∑_{b∈Θ_{j}} δ(b_{1}, x_{1}) ⋯ δ(b_{j}, x_{j}) b̃(zp_{b_{1}} ⋯ p_{b_{j}}) ,  (19)

where Θ_{j} = {0, 1}^{j}. This functional equation is easy to solve. Comparing the coefficients of L̃^{ω}(z) at z^{N}/N! we get

l̃_{N}^{ω} = \frac{(−1)^{N}(N − 1) ∑_{j=0}^{M−1} ∑_{b∈Θ_{j}} ∏_{i=1}^{j} δ(b_{i}, x_{i})p_{b_{i}}^{N}}{1 − ∑_{b∈Θ_{M}} ∏_{i=1}^{M} δ(b_{i}, x_{i})p_{b_{i}}^{N}} .  (20)

From the definition of δ(b_{i}, x_{i}) it follows that

∑_{b∈Θ_{j}} ∏_{i=1}^{j} δ(b_{i}, x_{i})p_{b_{i}}^{N} = (p_{0}^{1+N} + p_{1}^{1+N} )^{s_{j}} (p_{0}^{N} + p_{1}^{N} )^{j−s_{j}} =: P (N; s_{j})

where s_{j} is the number of components S among (x_{1}, …, x_{j}). Therefore, with s = s_{M},

l̃_{N}^{ω} = \frac{(−1)^{N}(N − 1) ∑_{j=0}^{M−1} P (N; s_{j})}{1 − P (N; s)},  N ≥ 1 .  (21)

To recover the original average cost l_{N}^{ω} we note that l_{N}^{ω} = ∑_{k=1}^{N} \binom{N}{k}l̃_{k}^{ω}.

The asymptotics of l_{N}^{ω} can now be obtained by a Mellin transform approach (cf. [23]) or Rice’s formula (compare Section 3.2). In particular, using [23] we translate l_{N}^{ω} into the following Mellin-like integral

l_{N}^{ω} = \frac{1}{2πi} ∫_{−3/2−i∞}^{−3/2+i∞} \frac{Γ(z)N^{−z}(z + 1) ∑_{j=0}^{M−1} P (−z; s_{j})}{1 − P (−z; s)}dz · (1 + O(\frac{1}{N})) .

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 < s < M the dominating pole is a simple pole at z = −κ_{0}. Additional simple poles occur at the nonreal zeroes of the denominator. It can be shown that nonreal zeroes at −κ_{0} + iy_{k} occur if and only if \frac{log p_{1}}{log p_{0}} is rational (compare the similar reasoning in [14]). They constitute the fluctuating function ξ(N). It is easy to prove that 0 < κ_{0} < 1.

In the deterministic case of a fixed query sequence σ = (x_{1}, x_{2}, …) ∈ {0, 1, ∗}^{∞} we iterate recurrence (8), observe

∑_{b∈Θ_{j}} ∏_{i=1}^{j} ε(b_{i}, x_{i})p_{b_{i}}^{N} = p_{0}^{Nn_{0}(σ_{j})}p_{1}^{Nn_{1}(σ_{j})} (p_{0}^{N} + p_{1}^{N} )^{n_{∗}(σ_{j})} =: Q(N, σ_{j}).

where σ_{j} = (x_{1}, x_{2}, …, x_{j}) and get the solution

l̃_{N}^{σ} = (−1)^{N}(N − 1) ∑_{j≥0} Q(N, σ_{j}).  (22)

For general σ a suitable analytic continuation of ∑_{j≥0} Q(z, σ_{j}) will not exist, but there is one for instance if σ has period k. Then

∑_{j≥0} Q(z, σ_{j}) = \frac{∑_{j=0}^{k−1} Q(z, σ_{j})}{1 − Q(z, σ_{k})}

is meromorphic and we obtain Theorem 1.2 by the same method as Theorem 1.1.

3.2 The Analysis of the Variance in the Symmetric Case

We first consider ω = (∗, S), S ∈ {0, 1}. Before attacking the second factorial moment of the cost C_{N}^{ω} we perform a more precise evaluation of the average cost l_{N}^{ω}.

From (21) we have

l_{N}^{ω} = ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}f(k) with f(z) = \frac{(z − 1)(1 + 2^{1−z})}{1 − 2^{1−2z}} .  (23)

The alternating sum can be treated by the following lemma.

Lemma. (Rice’s method, cf. [12], [17], [18]) Let C be a path surrounding the points {j, j + 1, …, N}, and f(z) be an analytical continuation of f(k) inside C. Then

∑_{k=j}^{N} \binom{N}{k}(−1)^{k}f(k) = −\frac{1}{2πi} ∫_{C}[N; z]f(z)dz ,  (24)

where

[N; z] = \frac{Γ(−z)Γ(N + 1)}{Γ(N + 1 − z)} = \frac{(−1)^{N−1}N!}{z(z − 1) ⋯ (z − N)} .  (25)

Extending the contour of the integration it can be shown that under suitable growth conditions for f(z) the alternating sum in (24) equals ∑ Res([N; z]f(z)) + O(N^{c}), where the sum is taken over all residues with real part greater than c that are different from j, …, N.

The function f(z) in (23) has single poles at z_{k} = \frac{1}{2} + \frac{1}{2}χ_{k} where χ_{k} = 2πik/L and L = log 2. Computing the residues at z_{k} and additionally at z = 0 (coming from the function [N; z]), we finally obtain

l_{N}^{ω} = \sqrt{N} (\sqrt{π} \frac{1 + \sqrt{2}}{2L} + τ^{ω} (log_{2} \sqrt{N})) − 3 + o(1),  (26)

where the fluctuating function τ^{ω}(x) = ∑_{k≠0} τ_{k}^{ω}e^{2kπix} has the Fourier coefficients

τ_{k}^{ω} = \frac{1}{2L} (1 + \sqrt{2}(−1)^{k}) Γ (\frac{−1 − χ_{k}}{2} ) (\frac{−1 + χ_{k}}{2} ) .  (27)

Now we deal with the second factorial moment. Let w_{N}^{ω} = (H_{N}^{ω})′′(1), and W^{ω}(z) be its exponential generating function. From now on we define Ã(z) = A(z)e^{−z} for any function A(z) under consideration. From (13), after differentiating it twice, we obtain

W̃^{ω}(z) = 2W̃^{ω′} (\frac{z}{2}) + 4L̃^{ω′} (\frac{z}{2}) + 2 (L̃^{ω′} (\frac{z}{2}))^{2}
W̃^{ω′}(z) = W̃^{ω} (\frac{z}{2}) + 2L̃^{ω} (\frac{z}{2}) .

For simplicity of presentation, W̃^{ω}(z) = R̃^{ω}(z) + T̃^{ω}(z) where

R̃^{ω}(z) = 2R̃^{ω′} (\frac{z}{2}) + 4L̃^{ω′} (\frac{z}{2}) ,  R̃^{ω′}(z) = R̃^{ω} (\frac{z}{2}) + 2L̃^{ω} (\frac{z}{2})  (28)

and

T̃^{ω}(z) = 2T̃^{ω′} (\frac{z}{2}) + 2 (L̃^{ω′} (\frac{z}{2}))^{2} ,  T̃^{ω′}(z) = T̃^{ω} (\frac{z}{2}) .  (29)

The solution of the first system of recurrences, namely (28), is easy. Note that it reduces to the following functional equation

R̃^{ω}(z) = 2R̃^{ω} (\frac{z}{4}) + 4L̃^{ω′} (\frac{z}{2}) + 4L̃^{ω} (\frac{z}{4}) .

Comparing coefficients we immediately find that

r̃_{N}^{ω} = \frac{(−1)^{N}(N − 1)2^{2−N}}{(1 − 2^{1−2N})^{2}} [1 + 2^{1−N} + 2^{1−2N} ] .  (30)

Now we deal with (29), which is more intricate. We need a formula for the coefficients of M̃^{ω′}(z) = (L̃^{ω′} (z))^{2} that avoids the convolution originating from the square. But from (19)

L̃^{ω′}(z) = 2L̃^{ω′} (\frac{z}{4}) + b̃(z) + b̃ (\frac{z}{2}) .

Taking it to the power two, we obtain

M̃^{ω′}(z) = 4M̃^{ω′} (\frac{z}{4}) + 4 (b̃(z) + b̃ (\frac{z}{2})) L̃^{ω′} (\frac{z}{4}) + (b̃(z) + b̃ (\frac{z}{2}))^{2} ,

which allows to express the coefficients of M̃^{ω′}(z) in the desired manner.

Putting everything together we find after some tedious algebra that w_{N}^{ω} = ∑_{k=2}^{N} \binom{N}{k}(−1)^{k}f(k) with f(z) as below

f(z) = \frac{(z − 1)2^{1−z}}{(1 − 2^{1−2z}) (1 − 2^{2−2z})} [5 + 2^{3−z} + 2^{3−2z} + z2^{z−2} − 2^{z} + \frac{z}{4} + (z − \frac{9}{2}) (\frac{3}{2})^{z−2}]
+ \frac{2^{3−2z}}{(1 − 2^{1−2z}) (1 − 2^{2−2z})} ∑_{l≥2} \binom{z}{l}\frac{(l − 1)(z − l − 1) (1 + 2^{−l}) (1 + 2^{z−l}) 2^{−l}}{1 − 2^{1−2l}} . (31)

Now we can apply our Lemma to the alternating sum w_{N}^{ω} to obtain an asymptotic expansion. Note that there are two sets of poles that contribute to the leading terms of the asymptotics. Namely, z_{k,1} = 1 + \frac{1}{2}χ_{k} and z_{k,2} = \frac{1}{2} + \frac{1}{2}χ_{k} where k = 0, ±1, · · · . Easy computations reveal finally that

w_{N}^{ω} ∼ \frac{N}{L} \{8 − \frac{7}{12} − 2 ∑_{l≥2}(−1)^{l} \frac{(1 + 2^{−l}) (1 + 2^{1−l}) 2^{−l}}{1 − 2^{1−2l}} + τ_{3}(log_{2} \sqrt{N})\}
− 2\sqrt{πN} \{\frac{1}{L} [\frac{73}{2\sqrt{2}} + \frac{25}{16} − \frac{4}{3\sqrt{3}}]  (32)
+ \frac{2}{L} ∑_{l≥2} \binom{1/2}{l}\frac{(l − 1) (l + \frac{1}{2}) (1 + 2^{−l}) 2^{−l}}{1 − 2^{\frac{1}{2} −l}} + τ_{4}(log_{2} \sqrt{N})\}

with periodic fluctuations τ_{3}(x) and τ_{4}(x) of mean (i.e. zeroeth Fourier coefficient) zero.

Now we are ready to put everything together. In particular, we note that, apart from continuous fluctuations of mean zero,

var C_{N}^{ω} = w_{N}^{ω} + l_{N}^{ω} − (l_{N}^{ω})^{2} = BN + A_{1}\sqrt{N} + o(\sqrt{N}) ,  (33)

where A_{1} and B are constants. Note that

B = \frac{1}{L} \{8 − \frac{7}{12} − 2 ∑_{l≥2}(−1)^{l} \frac{(1 + 2^{−l}) (1 + 2^{1−l}) 2^{−l}}{1 − 2^{1−2l}} \} − π \frac{(1 + \sqrt{2})^{2}}{4L^{2}} − [(τ^{ω})^{2}]_{0} ,

where [(τ^{ω})^{2}]_{0} is the mean of the square of the periodic function τ^{ω}(x) defined in (26). In the lines below we prove that B = 0. As in [17] and [18], we point out that the term [(τ^{ω})^{2}]_{0} significantly contributes to the cancellation of terms in B.

Considering the terms of order N, after having proved B = 0, the remaining fluctuating function has to be identically equal to zero since otherwise the variance would be negative for infinitely many values of N, which is impossible. For more detailed arguments the reader is referred to our papers [17] and [18].

To find a transformation for [(τ^{ω})^{2}]_{0} we proceed as follows. Note that

[(τ^{ω})^{2}]_{0} = 2 ∑_{k≥1} τ_{k}^{ω}τ_{−k}^{ω} = \frac{2}{4L^{2}} ∑_{k≥1} (3 + 2\sqrt{2}(−1)^{k}) Γ (\frac{1 − χ_{k}}{2} ) Γ (\frac{1 + χ_{k}}{2} ) .

Now we use the formula (cf. [1]) Γ(z)Γ(1 − z) = π/ sin πz and obtain

Γ(\frac{1 − χ_{k}}{2} )Γ(\frac{1 + χ_{k}}{2} ) = \frac{π}{sin(π/2 + ikπ^{2}/L)} = \frac{π}{cos(ikπ^{2}/L)} = \frac{π}{cosh(kπ^{2}/L)} = 2π \frac{e^{−kπ^{2}/L}}{1 + e^{−2kπ^{2}/L}} ,

so that

[(τ^{ω})^{2}]_{0} = \frac{π}{L^{2}} ∑_{k≥1} (3 + 2\sqrt{2}(−1)^{k}) \frac{e^{−kπ^{2}/L}}{1 + e^{−2kπ^{2}/L}} .  (34)

Let us define two new functions

F (x) = ∑_{k≥1} \frac{e^{−kx}}{1 + e^{−2kx}}  and G(x) = ∑_{k≥1} \frac{(−1)^{k−1}e^{−kx}}{1 + e^{−2kx}} .  (35)

Then, (34) in terms of F (x) and G(x) becomes

[(τ^{ω})^{2}]_{0} = \frac{3π}{L^{2}} F (\frac{π^{2}}{L} ) − \frac{2\sqrt{2}π}{L^{2}} G (\frac{π^{2}}{L} ) .  (36)

In order to prove B = 0, we use a series transformation for F (x) and G(x). We start with

F (x) = ∑_{j≥0}(−1)^{j} ∑_{k≥1} e^{−k(2j+1)x} = ∑_{j≥0} χ(j)\frac{1}{e^{jx} − 1}

where

χ(j) = \{ \begin{matrix}0 & for j even \\ 1 & for j ≡ 1 mod 4 \\ −1 & for j ≡ 3 mod 4 \end{matrix}

In [7] on page 258 we find the following Entry 11 from Ramanujan’s Notebooks.

For α, β > 0 such that αβ = π and y ∈ IR with |y| < β/2 the following holds

α \{\frac{1}{4} sec(αy) + ∑_{k=1}^{∞} χ(k)\frac{cos(αyk)}{e^{kα^{2}} − 1}\} = β \{\frac{1}{4} + \frac{1}{2} ∑_{k=1}^{∞} \frac{cosh(2βyk)}{cosh(kβ^{2})}\} .  (37)

For y = 0 this reads

α \{\frac{1}{4} + ∑_{k=1}^{∞} χ(k)\frac{1}{e^{kα^{2}} − 1}\} = β \{\frac{1}{4} + \frac{1}{2} ∑_{k=1}^{∞} \frac{1}{cosh(kβ^{2})}\} .

Replacing in the above cosh(x) by the exponential functions, expanding the geometric series and rearranging the sums we obtain

\frac{1}{2} ∑_{k≥1} \frac{1}{cosh(kβ^{2})} = ∑_{j≥1} χ(j)\frac{1}{e^{jβ^{2}} − 1} ,

so that, taking into account the constraint αβ = π, we find

α (\frac{1}{4} + F (α^{2})) = β (\frac{1}{4} + F (β^{2})) .

Now, we substitute in the above α = \sqrt{x} and β = π/\sqrt{x}. Then,

F (x) = \frac{π}{4x} − \frac{1}{4} + \frac{π}{x}F (\frac{π^{2}}{x} )  (38)

for x > 0, which is the desired transformation result. For G(x) we observe that G(x) = F (x) − 2F (2x), hence

G(x) = \frac{1}{4} + \frac{π}{x}F (\frac{π^{2}}{x} ) − \frac{π}{x}F (\frac{π^{2}}{2x}) .  (39)

Applying the above to (36) we finally obtain

[(τ^{ω})^{2}]_{0} = \frac{3}{4L} − \frac{π}{4L^{2}} (3 + 2\sqrt{2}) + \frac{3 − 2\sqrt{2}}{L}F (L) + \frac{2\sqrt{2}}{L}F (\frac{L}{2}) .  (40)

Using (40) B = 0 follows by some obvious simplifications. Thus, we have proved var C_{N}^{ω} = O(\sqrt{N}). The coefficient A_{1} at \sqrt{N} in (33) is given in Theorem 2(i) equation (16).

The second pattern ω = (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 ≥ 3. The reader should note that the key arguments in our proof of Theorem 2(i) are the transformations result (38) and (39). For M ≥ 3 there is no comparable result in 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 ≥ 3.

APPENDIX: Mellin Transform Approach to Ramanujan-Like Series Identities

Most proofs of results like Ramanujan’s formula (37) resp. (35) use the theory of modular functions (cf. [7]). In this appendix we outline the alternative approach using Mellin integrals, a line of attack, suggested to us by P. Flajolet, that belongs to the toolkit of analytic number theory (cf. [4]).

To prove (38) we proceed as follows. Let

β(s) = ∑_{j≥0}(−1)^{j} \frac{1}{(2j + 1)^{s}} .

Using definition (35) of F (x), we have

F (x) = ∑_{k≥1} \frac{e^{−kx}}{1 + e^{−2kx}} = ∑_{j≥0}(−1)^{j} ∑_{k≥1} e^{−k(2j+1)x} ,

so that the Mellin transform F^{∗}(s) = ∫_{0}^{∞} F (x)x^{s−1}dx of F (x) (cf. [9]) becomes

F^{∗}(s) = Γ(s)ζ(s)β(s) ,

where ζ(s) is Riemann’s zeta function [1]. By the Mellin inversion formula this yields

F (x) = \frac{1}{2πi} ∫_{3/2−i∞}^{3/2+i∞} Γ(s)ζ(s)β(s)x^{−s}ds .  (41)

Now we take the two residues s = 1 and s = 0 out from the above integral (observe that β(0) = 1/2 and β(1) = π/4 (cf. [1]) and apply the the duplication formula for Γ(s) to obtain

F (x) = \frac{π}{4x} − \frac{1}{4} + \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{1}{\sqrt{π}} 2^{s−1}Γ (\frac{s}{2}) Γ (\frac{s + 1}{2}) x^{−s}ζ(s)β(s)ds .

(Observe that the exponential smallness of the Γ-function along vertical lines justifies the shifting of the line integral.)

We now use the functional equations for ζ(s) and β(s), namely

Γ (\frac{s}{2}) ζ(s) = π^{s− \frac{1}{2}} Γ (\frac{1 − s}{2}) ζ(1 − s)  (42)

and

β(1 − s)Γ (1 − \frac{s}{2}) = 2^{2s−1}π^{−s+ \frac{1}{2}} Γ (\frac{s + 1}{2}) β(s) .  (43)

Identity (42) is Riemann’s functional equation for ζ(s), and (43) is an immediate consequence of the functional equation for Hurwitz’s ζ-function ζ(s, a) (cf. [3]), and the fact that

β(s) = 4^{−s} [ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})] .

Using (42) and (43), and substituting 1 − s = u, we get

F (x) = \frac{π}{4x} − \frac{1}{4} + \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞}π^{1−2u}Γ(u)x^{u−1}ζ(u)β(u)du .

This proves (38).

Using the above scheme several other identities can be proved. Below we just list some of them. Define

f(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} = ∑_{k≥1} \frac{k}{e^{kx} − 1},  (44)
g(x) = ∑_{k≥1} \frac{(−1)^{k−1}}{k (e^{kx} − 1)},  (45)
h(x) = ∑_{k≥1} \frac{1}{k (e^{2kπx} − 1)} .  (46)

Then, the following identities hold:

1.

1 + 2 ∑_{n≥1} e^{−πn^{2}x} = \frac{1}{\sqrt{x}} + \frac{2}{\sqrt{x}} ∑_{n≥1} e^{−πn^{2}/x} Jacobi’s ϑ–function,

f(x) = \frac{1}{x^{2}} \frac{π^{2}}{6} − \frac{1}{2x} + \frac{1}{24} − \frac{4π^{2}}{x^{2}} f (\frac{4π^{2}}{x} ) Ramanujan [7],

3.

g(x) = \frac{π^{2}}{12x} − \frac{log 2}{2} + \frac{x}{24} − g (\frac{2π^{2}}{x} ) Ramanujan [7],

4.

h(x) = \frac{π}{12} (\frac{1}{x} − x) + \frac{log x}{2} + h (\frac{1}{x}) Dedekind and Ramanujan [7].

The latter three identities play a prominent role in the analysis of the variance for some parameters of tries (cf. [15], [17], [18]). Remark. It is fairly well known that the functional equations for the Riemann ζfunction and the ϑ-function can be derived from each other via the Mellin transform (see e.g., [5], [8]). Here we would like to point out the analogous ϑ-like identity that is related to the functional equation for β(s). Let

H(x) = ∑_{j≥0}(−1)^{j}(2j + 1)e^{−(2j+1)^{2}x} , then H(x) = \frac{1}{8} (\frac{π}{x} )^{3/2} H (\frac{π^{2}}{16x}) .

ACKNOWLEDGMENTS

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.

References

[1] M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions, Dover, New York 1970.

[2] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading Mass. 1974.

[3] T. Apostol, Introduction to Analytical Number Theory, Springer-Verlag, New York 1976.

[4] T. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer-Verlag, New York 1978.

[5] R. Bellman, Analytic Number Theory – An Introduction, Benjamin-Cummings, London 1980.

[6] J. L. Bentley, Multidimensional Binary Search Trees Used for Associative Searching, Communication of the ACM, 18, 509-517, 1975.

[7] B.C. Berndt, Ramanujan’s Notebooks. Part II, Springer-Verlag, New York 1989.

[8] J. Borwein and P. Borwein, Pi and the AGM, John Wiley & Sons, New York 1987.

[9] B. Davis, Integral Transforms and Their Applications, Springer-Verlag, New York 1978.

[10] G.Fayolle, P.Flajolet and M.Hofri, On a functional equation arising in the analysis of a protocol for a multiaccess broadcast channel, Advances in Applied Probability, 18, 1986, 441–472.

[11] P. Flajolet and C. Puech, Partial Match Retrieval of Multidimensional Data, J. of the ACM, 33, 371-407, 1986.

[12] P. Flajolet and R. Sedgewick, Digital Search Trees Revisited, SIAM J. Computing, 15, 748-767, 1986.

[13] P. Henrici, Applied and Computational Complex Analysis, John Wiley&Sons, New York 1977.

[14] P. Jacquet, Contribution de l’Analyse d’Algorithmes à l’Évaluation des Protocoles de Communications, Thèse, Université de Paris Sud-Orsay, 1989.

[15] P. Kirschenhofer and H. Prodinger, On Some Applications of Formulae of Ramanujan in the Analysis of Algorithms, Mathematika, 38, 14-33, 1991.

[16] P. Kirschenhofer and H. Prodinger, Multidimensional Digital Searching – Alternative Data Structures, Proc. Random Graphs’91, John Wiley & Sons, 1992.

[17] P. Kirschenhofer, H. Prodinger and W. Szpankowski, On the Variance of the External Path length in a Symmetric Digital Tries, Discrete Applied Mathematics, 25, 129-143, 1989.

[18] P. Kirschenhofer, H. Prodinger and W. Szpankowski, On the balance Property of Patricia Tries: External Path Length Viewpoint, Theoretical Computer Science, 68, 1-17, 1989.

[19] D.E. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, Reading MA 1973.

[20] H. Mahmoud, Evolution of Random Search Trees, John Wiley & Sons, New York, 1992.

[21] M. Régnier and P. Jacquet, New Results on the Size of Tries, IEEE Trans. Information Theory, 35, 203-205 (1989).

[22] R. L. Rivest, Partial-Match Retrieval Algorithm, SIAM J. Computing, 5, 19-50, 1976.

[23] W. Szpankowski, The Evaluation of an Alternating Sum with Applications to the Analysis of Some Data Structures, Information Processing Letters, 28, 13-19, 1988.