A limit process for partial match queries in random quadtrees
A limit process for partial match queries in random quadtrees
复制标题
随机四叉树中部分匹配查询的限制过程
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Henning Sulzbach
中科院分区：
文献类型：
--
作者：
N. Broutin;Ralph Neininger;Henning Sulzbach
我们考虑在多维树（四叉树和k-d树）中恢复与部分指定模式匹配的项目的问题。我们假设经典模型中的数据由独立和均匀的点在单位正方形。对于该模型，在$n$个点的结构中，已知复杂度（以为了报告与随机查询$xi$匹配的独立且均匀分布在$[0，1]$上的项目而访问的节点$C_n（xi）$的数量来度量）满足$E{C_n（xi）}sim kappa n^{eta}$，其中$kappa$和$eta$是显式常数。我们在分析任意固定查询$sin [0，1]$的代价$Cn（s）$的基础上提出了一种方法，并给出了方差和极限分布的精确估计。在Skorokhod拓扑的c '{a} dl'{a}g函数空间中，导出了过程$（Cn（s））_{0 lesle 1}$的一个重标度形式的泛函极限律.对于最坏情况的复杂性$max_{sin [0，1]} C_n（s）$，给出了期望的阶和一个极限律。
We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quadtrees and k-d trees). We assume the classical 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 complexity, measured as the number of nodes $C_n(xi)$ to visit in order to report the items matching a random query $xi$, independent and uniformly distributed on $[0,1]$, satisfies $E{C_n(xi)}sim kappa n^{eta}$, where $kappa$ and $eta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(s)$ of any fixed query $sin [0,1]$, and give precise estimates for the variance and limit distribution. Moreover, a functional limit law for a rescaled version of the process $(C_n(s))_{0le sle 1}$ is derived in the space of c'{a}dl'{a}g functions with the Skorokhod topology. For the worst case complexity $max_{sin [0,1]} C_n(s)$ the order of the expectation as well as a limit law are given.