2011/07/12 by Nicolas Broutin, Broutin, Nicolas, Ralph Neininger +3
Computer Science · Mathematics · #05A15 #05A16 #05C05 #60C05 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DS #math.CO #math.PR #msc:05A15 #msc:05A16 #msc:05C05 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1107.2231
12 pages, 2 figures
arxiv created 2011/07/12 · arxiv updated 2011/07/13
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 Cn(ξ) to visit in order to report the items matching an independent and uniformly on [0,1] random query ξ satisfies \EcCn(ξ)∼ κnβ, where κ and β are explicit constants. We develop an approach based on the analysis of the cost Cn(x) of any fixed query x∈ [0,1], and give precise estimates for the variance and limit distribution of the cost Cn(x). Our results permit to describe a limit process for the costs Cn(x) as x varies in [0,1]; one of the consequences is that Emaxx∈ [0,1] Cn(x) ∼ γnβ.