概率天际线中有趣实例的识别

### 概率天际线中有趣实例的识别 在处理数据集中的概率天际线问题时，我们需要有效的方法来识别有趣的实例。为了实现这一目标，我们将介绍几种关键的数据结构和过滤方案。 #### 1. 概率范围树 为了界定和计算天际线概率，我们构建了两种类型的概率范围树：通用概率范围树（general - PRT，记为 $T_g$）和彩色概率范围树（colored - PRT）。 ##### 1.1 通用概率范围树 通用概率范围树 $T_g$ 是基于数据集 $S$ 中的所有 $n$ 个实例构建的。对于 $T_g$ 中信息列表 $L$ 里的第 $k$ 个实例 $p$（$p \in O_i$，$1 \leq i \leq m$），我们定义与 $p$ 相关的概率 $\beta_p$ 如下： $\beta_p = \prod_{i = 1}^{m}(1 - \sum_{q \in \hat{L}, q \in O_i}Pr(q))$ 其中，$\hat{L}$ 是 $L$ 中前 $k$ 个实例的列表。$\beta_p$ 表示 $\hat{L}$ 中没有实例存在的概率，即 $p$ 不存在且 $L$ 中 $p$ 之前的实例都不存在的概率。 创建信息列表 $L$ 时，我们将每个实例添加到 $L$ 中，然后按第 $d$ 维的值对所有实例进行排序。计算 $L$ 中每个 $p$ 的概率信息 $\beta_p$ 的步骤如下： - 使用 $s_i$ 记录在 $L$ 中已出现的对象 $O_i$ 的当前概率总和。 - 遍历 $L$ 中的实例，更新相应的概率总和，并根据 $L$ 中 $p$ 前一个实例的 $\beta$ 计算 $\beta_p$。 计算信息列表 $L$ 中所有 $\beta$ 的时间复杂度为 $O(|L|)$。 ##### 1.2 彩色概率范围树 除了基于 $S$ 中所有 $n$ 个实例构建的通用概率范围树，我们还有 $m$ 个特定的概率范围树，每个树基于相应对象的实例构建。如果为每个实例分配一种颜色以指示其来源，并将颜色 $i$ 与对象 $O_i$ 匹配，那么这些特定的概率范围树都只有一种颜色，因此我们称它们为彩色概率范围树。 彩色概率范围树的信息列表与列表中每个实例的概率总和相关。对于彩色概率范围树的信息列表 $L$ 中的第 $k$ 个实例 $p$，其概率总和 $\sigma_p = \sum_{q \in \hat{L}} Pr(q)$，其中 $\hat{L}$ 是 $L$ 中前 $k$ 个实例的列表。计算所有 $\sigma$ 的方法是遍历 $L$ 并累加概率总和，时间复杂度为 $O(|L|)$。 #### 2. 初步过滤方案 有了通用概率范围树和 $m$ 个彩色概率范围树后，我们可以利用它们计算天际线概率的边界，用于过滤实例。 ##### 2.1 上界计算 给定查询实例 $p$，我们可以通过查询通用概率范围树 $T_g$ 来获得 $Pr^+_{sky}(p)$。以下是 $d = 2$ 时的具体步骤： ```plaintext 输入: 通用 PRT $T_g$ 和查询实例 $p$ 输出: $Pr_{sky}(p)$ 的上界 1. 对 $p.D1$ 进行二分查找，找到搜索路径 $P$ 2. 在 $L_{root}$ 中对 $p.D2$ 进行二分查找，设位置为 $k$ 3. upperBound = 1 4. $v$ = root // 从根节点开始沿 $P$ 遍历 5. while 当前节点 $v$ 不是叶子节点 do 6. if 下一个节点 $w \in P$ 是 $v$ 的右子节点 then 7. $k'$ = $L_v[k].rankL$ 8. $u$ = $v$ 的左子节点 9. $\beta$ = $L_u[k']$.beta // 从 $v$ 的左子节点读取 $\beta$ 10. upperBound = upperBound * $\beta$ 11. $k$ = $L_v[k].rankR$ // 定位在 $L_w$ 中的位置 12. else // $w$ 是 $v$ 的左子节点 13. $k$ = $L_v[k].rankL$ // 定位在 $L_w$ 中的位置 14. end if 15. $v$ = $w$ // 向下移动一层 16. end while 17. return upperBound ``` 该算法的时间复杂度为 $O(\log n)$。对于 $d > 2$ 的情况，具体细节可参考相关技术报告。 ##### 2.2 更紧的上界 仅使用通用概率范围树可以得到天际线概率的上界，但结合通用概率范围树和彩色概率范围树可以得到更紧的上界。对于实例 $p \in O_k$，更紧的上界为： $\frac{\prod_{i = 1}^{t} \beta_i \cdot Pr(p)}{1 - \sum_{q \in O_k, q \prec p} Pr(q)} \geq Pr_{sky}(p)$ 其中，$\prod_{i = 1}^{t} \beta_i$ 是通过查询通用概率范围树得到的上界。为了得到更紧的上界，我们需要计算 $\sum_{q \in O_k, q \prec p} Pr(q)$，这可以通过查询颜色为 $k$ 的彩色概率范围树来实现。计算该总和的算法与计算通用概率范围树上界的算法类似，只是在搜索路径上累加概率而不是相乘。 ##### 2.3 下界计算 对于二维情况，对于每个实例 $(x, y)$，我们定义 $s_{iL}(x)$（分别地，$s_{