MULTIDIMENSIONAL DIGITAL SEARCHING –

ALTERNATIVE DATA STRUCTURES

Peter Kirschenhofer† and Helmut Prodinger†

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. We analyze the average cost of partial match queries in M–dimensional Digital Search Trees and Patricia Tries. Our results allow a precise comparison of the average behaviour of these data structures with the M–dimensional Tries studied by Flajolet and Puech [1]. It turns out that Patricia is superior to Digital Search Trees, the latter ones being superior to Tries.

1. Introduction and Main Results

Random trees under the Bernoulli model occur frequently in connection with data structures in Computer Science. In this paper we concentrate on some aspects of multidimensional search trees. The manipulation of multidimensional data is of vital importance with respect to the construction of database systems and applications, where we mention e.g. graphical algorithms. See Flajolet/Puech [1] for an exhaustive list of references on the subject. One of the important data structures in this context are the so–called M–dimensional tries, ”M–tries” for short:

The principle of the construction of tries (and other related data structures) is that digital properties of keys are used to build up a tree: In the basic case the keys are thought to be 0,1–sequences, where 0 and 1 occur with equal probability, and the keys are stored in the external nodes (leaves) of a binary tree, according to their shortest unique prefix among the other keys. (See Knuth [3] for details.)

The M–tries follow the same principle, but now the keys are M–tuples of 0,1– sequences, e.g.

K_{1} = (K_{11}, …, K_{1M})
⋮
K_{N} = (K_{N1}, …, K_{NM})

with all K_{ij} infinite 0,1–sequences.

To build up the M–trie the M sequences K_{i1}, …, K_{iM} corresponding to key K_{i} are ”shuffled” to yield one binary sequence K′_{i}, and the sequences K′_{1}, …, K′_{N} are used to build up a regular trie:

Typeset by AMS-TEX

†This research was supported by Fonds zur Förderung der Wissenschaftlichen Forschung Projekt No. P7497-TEC

2 PETER KIRSCHENHOFER† AND HELMUT PRODINGER†

More precisely, if K_{ij} = (K_{ij}^{(0)}, K_{ij}^{(1)}, K_{ij}^{(2)}, …), then

K′_{i} = (K_{i1}^{(0)}, …, K_{iM}^{(0)}, K_{i1}^{(1)}, …, K_{iM}^{(1)}, K_{i1}^{(2)}, …) .

Example. M=2

\begin{matrix}K_{1} = (01 …, 00 …) & ⟶ K′_{1} = (0010 …) \\ K_{2} = (10 …, 01 …) & ⟶ K′_{2} = (1001 …) \\ K_{3} = (11 …, 00 …) & ⟶ K′_{3} = (1010 …) \end{matrix}

2–trie:

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

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

Theorem T. ([1])

\begin{aligned}l_{ω,N}^{[T]} ∼ N^{1− \frac{s}{M}} · \{ & \frac{s}{M^{2}L} · \frac{Γ (\frac{s}{M} )}{1 − \frac{s}{M}} · ∑_{j=0}^{M−1} (δ_{1}δ_{2} … δ_{j}) 2^{−j(1−s/M)} \\ & + δ_{ω}^{[T]} (log_{2} N^{1/M}) \}, \end{aligned}

where s is the number of specified attributes in ω, 1 ≤ s ≤ M − 1, L = log 2, δ_{i} = 1 resp. 2 according to the i–th attribute in ω being specified resp. unspecified, and δ_{ω}^{[T]} (x) a continuous periodic function of mean zero with small amplitude. □

Similar results have been developed in [1] for binary search trees and grid file algorithms.

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

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

Example. With K_{1}, K_{2}, K_{3} from the last example we get the 2–DST

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

Theorem D.

l_{ω,N}^{[D]} ∼ N^{1− \frac{s}{M}} · \{\frac{Q (2^{1− \frac{s}{M}} )}{Q_{∞}} · \frac{1}{ML} · \frac{Γ (\frac{s}{M} )}{1 − \frac{s}{M}}×

× ∑_{j=0}^{M−1} (δ_{1}δ_{2} … δ_{j}) 2^{−j(1−s/M)}

+ δ_{ω}^{[D]} (log_{2} N^{1/M}) },

where Q(t) = ∏_{j≥1} (1 − \frac{t}{2^{j}} ) and Q_{∞} = Q(1). □

The basic idea of Patricia Tries is to compress one–way branches in Tries:

Example. With K_{1}, K_{2}, K_{3} from above we get the 2–Patricia Trie

Our result for this instance is

Theorem P.

l_{ω,N}^{[P]} ∼ N^{1− \frac{s}{M}} · \{ (\frac{s}{M} + 1) · (1 − 2^{−s/M}) · \frac{1}{ML} · \frac{Γ (\frac{s}{M} )}{1 − \frac{s}{M}}×

× ∑_{j=0}^{M−1} (δ_{1}δ_{2} … δ_{j}) 2^{−j(1−s/M)}

+ δ_{ω}^{[P]} (log_{2} N^{1/M}) }. □

Theorems T, D and P allow a precise comparison of the average cost of partial match queries in the concerned data structures: Neglecting the small periodic fluctuations the

Comparison Inequality

(1 + x) (1 − 2^{−x}) < \frac{Q (2^{1−x})}{Q_{∞}} < x for 0 < x < 1

ensures that

l_{ω,N}^{[P]} ⪯ l_{ω,N}^{[D]} ⪯ l_{ω,N}^{[T]}

for all query patterns ω. In Section 5 we give a proof of this comparison result.

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

In the following table we present the constants in question for the instance M = 2 and the two possible query patterns ω_{1} = ∗S and ω_{2} = S∗: (In both cases we have s = 1, so that the order of l_{N} is \sqrt{N}.)

T  D  P
ω_{1} = ∗S  3.0867 …  2.7768 …  2.7122 …
ω_{2} = S∗  2.1826 …  1.9635 …  1.9178 …

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

Theorem B.

l_{ω,N}^{[B]} ∼ N^{1− \frac{s}{M}} · \{\binom{\frac{s}{M} + b − 1}{b} · \frac{1}{ML} · \frac{Γ (\frac{s}{M} )}{1 − \frac{s}{M}}×

× ∑_{j=0}^{M−1} (δ_{1}δ_{2} … δ_{j}) 2^{−j(1−s/M)}

+ δ_{ω}^{[B]} (log_{2} N^{1/M}) }. □

This result can be compared with the result for grid–file–algorithms in Flajolet/Puech [1], where they use the same data structure but a different cost measure.

2. Digital Search Trees

Let ω be a fixed query pattern and ω′ the (cyclic) shift of ω, i.e. for ω = w_{1}w_{2} … w_{M} we have ω′ = w_{2} … w_{M}w_{1}. Obviously, ω^{(M)} = ω. We further denote the probability generating function for the cost with query pattern ω and N records by H_{ω,N}(z). From the construction of the M–dimensional Digital Search Trees in Section 1, we find immediately the following pair of recursions (the reader should remember that we always consider the Bernoulli model):

H_{ω,N+1}(z) = z ∑_{k=0}^{N} 2^{−N} \binom{N}{k}H_{ω′,k}(z) · \{ \begin{matrix}H_{ω′,N−k}(z) for ω = ∗ν \\ 1 for ω = Sν \end{matrix}

for N ≥ 0, H_{ω,0}(z) = 1.

The expectations of cost l_{ω,N} = l_{ω,N}^{[D]} are given by H′_{ω,N}(1), so that the recursion translates into

l_{ω,N+1} = 1 + δ_{1}2^{−N} ∑_{k=0}^{N} \binom{N}{k}l_{ω′,k}, for N ≥ 0, l_{ω,0} = 0,

where δ_{i} = 2 resp. 1 referring to w_{i} = ∗ resp. S in ω.

Thus the exponential generating functions

L_{ω}(z) = ∑_{N≥0} l_{ω,N} \frac{z^{N}}{N!}

fulfill the differential–functional equations

L′_{ω}(z) = e^{z} + δ_{1}e^{z/2}L_{ω′} (\frac{z}{2}) .

In order to solve it is convenient to introduce

L̃_{ω}(z) = e^{−z}L_{ω}(z),

so that

L̃′_{ω}(z) + L̃_{ω}(z) = 1 + δ_{1}L̃_{ω′} (\frac{z}{2}) .

Comparing coefficients we find

l̃_{ω,N+1} = − (l̃_{ω,N} − δ_{1}2^{−N} l̃_{ω′,N}) , N ≥ 1

with l̃_{ω,0} = 0, l̃_{ω,1} = 1. This recurrence has the solution

l̃_{ω,N+1} = (−1)^{N}( ∏_{j=1}^{N} (1 − 2^{−j}t) )|_{t^{r}→δ_{1}δ_{2}...δ_{r}} =: (−1)^{N}Q_{ω,N}

where δ_{A·M+r} = δ_{r}.

We finally get the explicit solution

l_{ω,N}^{[D]} = − ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}Q_{ω,k−1}.

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

Lemma. Let C be a path surrounding the points j, j+1, …, N and f(z) be analytic inside C and continuous on C. Then

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

with [N; z] = \frac{(−1)^{N−1}N!}{z(z−1)...(z−N)}. □

Moving the contour of integration, one can obtain the asymptotic expansion of the alternating sum by Cauchy’s residue theorem: Under certain growth conditions for f(z), which are fulfilled in our instance,

∑_{k≥j} \binom{N}{k}(−1)^{k}f(k)

may be asymptotically evaluated by

∑ Res([N; z]f(z))

where the sum is taken over the set of poles z different from j, j + 1, …, N.

In our instance we have

f(k) = Q_{ω,k−1},

so that we need an analytic continuation of this discrete sequence. Omitting the details the idea is as follows:

Using partial fraction decomposition we have

∏_{j=1}^{N} (1 − 2^{−j}t) = \frac{Q(t)}{Q_{∞}} ∑_{i≥1} a_{i} \frac{1}{1 − t2^{−i−N}}

where

Q(t) = ∏_{j≥1} (1 − 2^{−j}t) , Q_{∞} = Q(1) and a_{i} = (−1)^{i−1}2^{−\binom{i}{2}}/Q_{i−1}.

Using Euler’s product identity

Q(t) = ∑_{n≥0} a_{n+1}t^{n}

and expanding the geometric series in t we get

∏_{j=1}^{N} (1 − 2^{−j}t) = \frac{1}{Q_{∞}} ∑_{m≥0} t^{m} ∑_{i≥1} a_{i} ∑_{r=0}^{m} a_{m−r+1}2^{−r(N+i)}.

Since this is an identity for analytic functions in t, the coefficients of t^{m} must coincide, and we are allowed to substitute t^{m} by δ_{1} … δ_{m} in both sides, simultanously. We get

Q_{ω,N} = \frac{1}{Q_{∞}} ∑_{m≥0} δ_{1} … δ_{m} ∑_{i≥1} a_{i} ∑_{r=0}^{m} a_{m−r+1}2^{−r(N+i)}.

Now, for m = A · M + j,

δ_{1} … δ_{m} = 2^{A(M−s)} · δ_{1} … δ_{j}

so that, after rearranging the sums,

\begin{aligned}Q_{ω,N} = \frac{1}{Q_{∞}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} & ∑_{i≥1} a_{i} ∑_{h≥0} a_{h+1}2^{(h−j)(N+i)}× \\ & × ∑_{A≥max(0, \frac{h−j}{M})} 2^{−A(M(N+i−1)+s)} \end{aligned}

and, by replacing N by z, we have

\begin{matrix}Q_{ω,z} = \frac{1}{Q_{∞}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} ∑_{i≥1} a_{i} \frac{1}{1 − 2^{−M(z+i−1)−s}} × \\ × \{∑_{h=0}^{j−1} a_{h+1}2^{(h−j)(z+i)} + ∑_{h≥j} a_{h+1}2^{(h−j)(z+i)−⌈ \frac{h−j}{M} ⌉·(M(z+i−1)−s)}\} . \end{matrix}

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

[N; 1 − \frac{s}{M} ] \frac{1}{Q_{∞}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} ∑_{h≥0} a_{h+1}2^{(h−j)(1− \frac{s}{M})} · \frac{1}{ML}

(L = log 2). Using again Euler’s product identity we get

[N; 1 − \frac{s}{M} ] \frac{1}{Q_{∞}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−j(1− \frac{s}{M})}Q (2^{1− \frac{s}{M}} ) \frac{1}{ML}.

Since

\begin{aligned}[N; 1 − \frac{s}{M} ] & = Γ (−1 + \frac{s}{M} ) · Γ(N + 1)/Γ (N + \frac{s}{M} ) \\ & ∼ N^{1− \frac{s}{M}} · Γ (−1 + \frac{s}{M} ) \end{aligned}

we get the main term in Theorem D.

The periodic fluctuation δ_{ω}^{[D]} originates from the simple poles at 1 − \frac{s}{M} + \frac{2kπi}{LM}; in principle one can get the Fourier expansion of δ_{ω}^{[D]}(x) by collecting the residues at these poles, but we omit the details here.

3. Patricia Tries

With the notations of Section 2 we may proceed with this instance as follows: The probability generating functions of cost fulfill for N ≥ 2

\begin{aligned}H_{ω,N}(z) & = z ∑_{k=0}^{N} 2^{−N} \binom{N}{k}H_{ω′,k}(z) · \{ \begin{matrix}H_{ω′,N−k}(z) \\ 1 \end{matrix}\} \\ & − (z − 1)δ_{1} 2^{−N}H_{ω′,N}(z), \end{aligned}

H_{ω,0}(z) = H_{ω,1}(z) = 1.

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

The average costs are given by

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

for N ≥ 2.

This time the functions L̃_{ω}(z) fulfill a system of functional equations

L̃_{ω}(z) = g_{1}(z) + δ_{1}L̃_{ω′} (\frac{z}{2}) ,

where

g_{i}(z) = 1 − (1 + z)e^{−z} − δ_{i} (e^{−z/2} − (1 + \frac{z}{2}) e^{−z}) .

The system may be solved by iteration and gives us

l̃_{ω,N} = \frac{1}{1 − 2^{M(1−N−s/M)}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−jN} [\frac{z^{N}}{N!} ] g_{j+1}(z).

Now

[\frac{z^{N}}{N!} ] g_{j+1}(z) = (−1)^{N} (N − 1 − δ_{j+1} (2^{−N} + \frac{N}{2} − 1)) ,

so that

l_{ω,N} = ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}f(k)

MULTIDIMENSIONAL DIGITAL SEARCHING – ALTERNATIVE DATA STRUCTURES 9

with

\begin{aligned}f(z) & = \frac{1}{1 − 2^{M(1−z−s/M)}} × \\ & × ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−jz} (z − 1 − δ_{j+1} (2^{−z} + \frac{z}{2} − 1)) . \end{aligned}

Collecting the residues of [N; z]f(z) at z = 1 − s/M we get the main contribution

\begin{aligned}N^{1− \frac{s}{M}} · \frac{−1}{ML}Γ (\frac{s}{M} − 1) & ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−j(1−s/M)}× \\ & × [\frac{s}{M} − \frac{δ_{j+1}}{2} (1 + \frac{s}{M} − 2^{s/M})] . \end{aligned}

The sum can be rearranged as follows:

∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−j(1−s/M)} · \frac{s}{M}

− \frac{1}{2} ∑_{j=1}^{M} δ_{1} … δ_{j} 2^{−j(1−s/M)} · 2^{1−s/M} (1 + \frac{s}{M} − 2^{s/M})

= ∑_{j=1}^{M−1} δ_{1} … δ_{j} 2^{−j(1−s/M)} · (\frac{s}{M} − 2^{−s/M} (1 + \frac{s}{M} − 2^{s/M}))

+ \frac{s}{M} − \frac{1}{2}2^{M−s−M(1−s/M)+1−s/M} (1 + \frac{s}{M} − 2^{s/M}) ,

since δ_{1} … δ_{M} = 2^{M−s}, and furthermore

= (\frac{s}{M} + 1) (1 − 2^{−s/M}) ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−j(1−s/M)}.

From the last observation Theorem P is immediate.

5. The Comparison Inequality

Let f(x) = Q (2^{−x}) /Q_{∞}. It is easily seen that the left–hand side of the inequality is equivalent to

(i)  1 + x < f(x) for 0 < x < 1

and the right–hand side to

(ii)  f(x) < 1 + x for − 1 < x < 0.

Now

f(x) = ∏_{j≥1} (1 + \frac{1 − 2^{−x}}{2^{j} − 1} ) = P (y)

where y = 1 − 2^{−x} fulfills (i) 0 < y < \frac{1}{2} resp. (ii) −1 < y < 0.

Let

g(y) = \frac{1 + x}{f(x)} = \frac{1 − log_{2}(1 − y)}{P (y)}.

Since g(0) = g (\frac{1}{2}) = 1, it is sufficient to prove that g(y) is a logarithmically convex function in y for −1 < y < \frac{1}{2}: With h(y) = log g(y) we find

h′′(y) = \frac{1}{(1 − y)^{2}} · \{\frac{1}{log (\frac{2}{1−y} )} − \frac{1}{log^{2} (\frac{2}{1−y} )} + ∑_{j≥1} (\frac{2^{j}}{1 − y} − 1)^{−2}\} .

The expression in brackets should be positive, which is (with z = 1 + x = 1 − log_{2}(1 − y)) equivalent to

∑_{j≥0} (2^{j+z} − 1)^{−2} > \frac{1}{L^{2}z^{2}} − \frac{1}{Lz} , 0 < z < 2.

The last inequality is trivial for z ≥ 1/L, since the right–hand side is < 0, and is a fortiori proved for 0 < z < 1/L by

(\frac{2^{z} − 1}{Lz})^{2} < \frac{1}{1 − Lz} ,

which may be seen directly by comparing the Taylor coefficients of both sides.

6. b–Tries

Here we have for the probability generating function

H_{ω,N}(z) = z ∑_{k=0}^{N} 2^{−N} \binom{N}{k}H_{ω′,k}(z) · \{ \begin{matrix}H_{ω′,N−k}(z) \\ 1 \end{matrix}\}

for N ≥ b + 1, H_{ω,0}(z) = ⋯ = H_{ω,b}(z) = 1.

The functional equations for L̃_{ω}(z) read

L̃_{ω}(z) = 1 − e_{b}(z) · e^{−z} + δ_{1}L̃_{ω′} (\frac{z}{2})

where

e_{b}(z) = ∑_{i=0}^{b} \frac{z^{i}}{i!} .

Iteration of the system and comparing coefficients yields

l_{ω,N} = ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}f(k)

with

f(z) = \frac{(−1)^{b+1}\binom{z−1}{b}}{1 − 2^{M(1−z−s/M)}} ∑_{j=0}^{M−1} δ_{1} … δ_{j} 2^{−jz}.

Calculating the residues at the dominating poles we find Theorem B by some easy manipulations.

References

1. P. Flajolet, C. Puech, Partial match retrieval of multidimensional data, Journal ACM 33 (1986), 371–507.

2. P.Flajolet, R.Sedgewick, Digital Search Trees Revisited, SIAM J. Comput. 15 (1986), 748–767.

3. D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973.

4. N.E.Nörlund, Vorlesungen über Differenzenrechnung, Chelsea, New York, 1954.

TU Vienna, Wiedner Hauptstraße 8-10, A-1040 Vienna, Austria