Abstract
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.
Citation
Ralph Neininger. Ludger Rüschendorf. "Limit laws for partial match queries in quadtrees." Ann. Appl. Probab. 11 (2) 452 - 469, May 2001. https://doi.org/10.1214/aoap/1015345300
Information