支持范围查询的不确定数据索引

### 支持范围查询的不确定数据索引 在处理不确定数据的概率范围查询时，高效的索引技术至关重要。本文将介绍几种现有的索引方法，并提出一种新的多分辨率摘要树（MRST）和基于此的R - MRST索引，以解决现有方法存在的问题。 #### 现有索引方法回顾 近年来，为了回答不确定数据上的概率范围查询，提出了许多有效的索引。以下是几种常见的索引及其特点： | 索引名称 | 技术原理 | 优点 | 缺点 | | ---- | ---- | ---- | ---- | | U - Tree | 采用PCR（概率约束区域）技术总结不确定对象的概率密度函数（PDF），并使用R - tree技术组织PCRs | - | PCR过滤能力不强，动态更新成本高 | | UI - Tree和UD - Tree | 采用分区技术总结不确定对象的PDF，对每个对象的不确定区域进行分区，预计算分区子区域的出现概率，并使用R - tree技术组织这些子区域 | 过滤能力比U - Tree强 | 空间成本高，分区未反映PDF梯度，过滤算法未考虑查询区域与子区域的交集面积 | ##### U - Tree详细介绍 U - Tree为每个对象构建一组PCRs，并使用R - tree技术进行组织。以二维空间为例，给定一个对象o和概率阈值θ（0 < θ < 0.5），o.PCR(θ)的构建过程如下： 1. 在水平维度上，计算两条线l1和l2，使得对象o在l1左侧（l2右侧）出现的概率为θ。 2. 在垂直维度上，以相同方式计算两条线l3和l4。 3. o.PCR(θ)是由这四条线围成的矩形。 给定一个概率查询q，若查询阈值qp ≤ θ，当qp ≥ θ时，o.PCR(θ)用于修剪/验证对象。然而，当查询区域与对象重叠但不能包含d维空间中对象的d - 1维平面时，PCR的修剪/验证能力不强。并且，由于每个对象使用一组PCR来总结其PDF，U - Tree的节点需要使用一组最小边界矩形（MBR）来包围这些PCR，动态更新时维护这些边界的成本比R - Tree高。 ##### UI - Tree和UD - Tree详细介绍 为了构建每个对象PDF的摘要，UI - Tree的关键思想是对每个对象的不确定区域进行分区，预计算分区子区域的出现概率，并使用R - tree技术组织这些子区域。给定一个概率范围查询，UI - Tree检索与查询区域重叠的子区域，找到相应的对象，然后计算对象o出现在查询区域的概率app(o, q)的上下界。具体来说： 1. 如果子区域o(i)包含在查询区域qr中，app(o, i)对app(o, q)的上下界都有贡献。 2. 如果子区域o(j)与查询区域qr重叠，app(o, j)对app(o, q)的上界有贡献。 然后根据app(o, q)的下界（上界）来验证（修剪）对象o。虽然UI - Tree的修剪能力比U - Tree强，但空间成本过高，且分区未反映PDF的梯度，过滤算法未考虑查询区域与子区域的交集面积。 #### 问题定义 给定一个d维空间中的多维概率对象o，它可以连续或离散地描述： - **连续情况**：对象o有两个属性，概率区域or和概率密度函数o.pdf(x)。or是一个d维的不确定区域，对象o可以以一定概率出现在其中的任何位置。o.pdf(x)是对象o出现在位置x的概率。 - **离散情况**：对象o由一组采样点x1, x2, ..., xm表示，对象o在位置xi出现的概率为xi.p。 给定一个查询区域qr，使用app(o, q)表示对象o落在查询区域qr中的可能性，其计算方式也分为两种情况： - **连续情况**： \[app(o, q) = \int_{or \cap qr} o.pdf(x) dx\] 当app(o, q) ≥ θ（查询概率阈值）时，对象o是查询结果。 - **离散情况**： \[app(o, q) = \frac{\sum_{i = 1}^{n2} o.pdf(xi)}{\sum_{i = 1}^{n1} o.pdf(xi)}\] 其中n1是or中采样点的数量，n2是落在or ∩ qr中的采样点的数量。 **概率范围查询定义**：给定一组概率对象O和一个范围查询q，概率范围查询检索所有满足app(o, q) ≥ θ的概率对象o，其中θ是概率阈值，0 ≤ θ ≤ 1。 #### MRST：多分辨率摘要树 为了解决现有索引方法的问题，我们提出了一种新的摘要方法——多分辨率摘要树（MRST），用于近似捕获不确定对象的PDF。MRST充分考虑了PDF的梯度，能更有效地捕获对象的PDF，具有更强的过滤能力和更低的空间成本。以下是关于MRST的详细介绍： ##### 紧密概率边界用于过滤 为了给对象提供紧密的边界，我们首先讨论如何为每个子区域o(i)提供紧密的边界。给定一个对象o、一个子区域o(i)和一个查询q，如果查询区域qr与o(i).MBR重叠，以下两个公式分别给出了对象o落在or ∩ qr中的概率下界和上界： \[lbapp(q, i) = lb(o, i) \times (max(0, S(q, i) - ZS(o, i)))\] \[ubapp(q, i