Asymptotic distributions for partial match queries inK-d trees
Ralph Neininger · Random Structures and Algorithms · 2000
The distributional performance of the cost of a partial match query is investigated in some sorts of K-d trees. The trees under consideration are Bentley's K-d tree, the locally balanced K-d-t tree, and the random relaxed K-d tree. For each of these trees it is proved that in the uniform probabilistic model the normalized cost of a partial match query converges in distribution. The limiting distributions occur as fixed points of random affine operators. Also explicit first-order asymptotic expansions for the variances of the costs and results on exponential moments are derived. The analysis is based on the contraction method. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 403–427, 2000