Asymptotic distributions for partial match queries in K-d trees

✍ Scribed by Ralph Neininger

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 229 KB
• Volume: 17
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/1098-2418(200010/12)17:3/4<403::aid-rsa11>3.0.co;2-k

✦ Synopsis

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.