We analyze the mean cost of the partial match queries in random two-dimensional
quadtrees. The method is based on fragmentation theory. The convergence is
guaranteed by a coupling argument of Markov chains, whereas the value of the
limit is computed as the fixed point of an integral equation.
Publié le : 2011-03-15
Classification:
Quadtree,
partial match query,
fragmentation theory,
Markov chain,
coupling,
integral equation,
60F99,
60G18,
60J05
@article{1300198518,
author = {Curien, Nicolas and Joseph, Adrien},
title = {Partial match queries in two-dimensional quadtrees: a probabilistic approach},
journal = {Adv. in Appl. Probab.},
volume = {43},
number = {1},
year = {2011},
pages = { 178-194},
language = {en},
url = {http://dml.mathdoc.fr/item/1300198518}
}
Curien, Nicolas; Joseph, Adrien. Partial match queries in two-dimensional quadtrees: a probabilistic approach. Adv. in Appl. Probab., Tome 43 (2011) no. 1, pp. 178-194. http://gdmltest.u-ga.fr/item/1300198518/