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.
Publié le : 2001-05-14
Classification:
Quadtree,
partial match query,
contraction method,
multidimensional data structure,
analysis of algorithms,
68Q25,
60F05,
68P10
@article{1015345300,
author = {Neininger, Ralph and R\"uschendorf, Ludger},
title = {Limit laws for partial match queries in quadtrees},
journal = {Ann. Appl. Probab.},
volume = {11},
number = {2},
year = {2001},
pages = { 452-469},
language = {en},
url = {http://dml.mathdoc.fr/item/1015345300}
}
Neininger, Ralph; Rüschendorf, Ludger. Limit laws for partial match queries in quadtrees. Ann. Appl. Probab., Tome 11 (2001) no. 2, pp. 452-469. http://gdmltest.u-ga.fr/item/1015345300/