Hua-Huai Félix Chern: Partial Match Queries in Random Quadtrees

This is a joint work with Hsien-Kuei Hwang.

A major open problem for the analysis of partial-match queries in random quadtrees is the determination of the leading constants of the expected cost. More precisely, it is known (see [FGPR93]) that the expected cost, say $Q_n^{(d,s)}$, of a random partial-match query in a random quadtree of $n$ keys (chosen uniformly i.i.d. from the hypercube $[0,1]^d$) satisfies $Q_n^{(d,s)} \sim c_{d,s} n^{\alpha-1}$, where $\alpha$ is the zero of the indicial equation $x^{d-s}(x+1)^{s}=2^d$ with the largest real part, $s$ being the number of specified coordinates in the random query. But the exact value of $c_{d,s}$ is unknown for $d\ge3$. We propose a means of deriving expressions for $c_{d,s}$. The approach is based on extending our recent tools for Cauchy-Euler equations. In the special cases when only one coordinate is specified or unspecified, the constant $c_{d,1}$ or $c_{d,d-1}$ can be computed in a more explicit way in terms of hypergeometric functions. Our approach is also applicable to k-d trees.

Bibliography

FGPR93

Philippe Flajolet, Gaston Gonnet, Claude Puech, and John Michael Robson.
Analytic variations on quadtrees.
Algorithmica, 10(6):473-500, 1993.

FLLS95

Philippe Flajolet, Gilbert Labelle, Louise Laforest, and Bruno Salvy.
Hypergeometrics and the cost structure of quadtrees.
Random Structures Algorithms, 7(2):117-144, 1995.

Back to the Index