Limit laws for partial match queries in quadtrees

• 成果类型: Article
• 署名作者: Neininger, R; Rüschendorf, L
• 署名单位: University of Freiburg
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2001
• 页码: 452-469
• 关键词: path-length; distributions; quicksort; THEOREM; trees

摘要

It is proved that in an idealized uniform probabilistic model the cost of a partial match query in a multidimensional quadtree after normalization converges in distribution. The limiting distribution is given as a fixed point of a random affine operator. Also a first-order asymptotic expansion for the variance of the cost is derived and results on exponential moments are given. The analysis is based on the contraction method.