Hsien-Kuei Hwang: Partial Match Queries in Random $k$-$d$ trees

This is a joint work with Hua-Huai Chern.

We propose an analytic approach for the average-case analysis of (random) partial match queries in random k-d trees. We use a more straightforward analysis based on a single differential equation instead of the linear system used by Flajolet and Puech [FP86]. Then our theory for "perturbed" Cauchy-Euler differential equations can be applied to derive the required asymptotics, with analytic expressions for the leading constants. The leading constants can in some special cases be expressed more explicitly in terms of known (like Gamma or hypergeometric) functions.

Bibliography

FP86

Philippe Flajolet and Claude Puech.
Partial match retrieval of multidimensional data.
J. Assoc. Comput. Mach., 33(2):371-407, 1986.

Back to the Index