Partial match queries in random quadtrees

Details Partial match queries in random quadtrees Partial match queries in random quadtrees

2011-07-12

arxiv.org/abs/1107.2231v1

Mathematics

Probability

12 pages, 2 figures

Scientific paper

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the data consist of independent and uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the number of nodes $C_n(\xi)$ to visit in order to report the items matching an independent and uniformly on $[0,1]$ random query $\xi$ satisfies $\Ec{C_n(\xi)}\sim \kappa n^{\beta}$, where $\kappa$ and $\beta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(x)$ of any fixed query $x\in [0,1]$, and give precise estimates for the variance and limit distribution of the cost $C_n(x)$. Our results permit to describe a limit process for the costs $C_n(x)$ as $x$ varies in $[0,1]$; one of the consequences is that $E{\max_{x\in [0,1]} C_n(x)} \sim \gamma n^\beta$.

Affiliated with

Also associated with

No associations

Rating

Partial match queries in random quadtrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Partial match queries in random quadtrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partial match queries in random quadtrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565272