排序和天际线查询处理框架解析

### 排序和天际线查询处理框架解析 在数据处理领域，排序和天际线查询是非常重要的操作。本文将深入探讨排序和天际线查询的处理框架，包括相关概念的定义、现有算法的局限性以及成本优化策略等内容。 #### 1. 排序和天际线查询处理概述 在某些场景下，如果某个属性的排序访问成本较低，特定的处理方式会更有效。经验结果表明，基于成本的优化方法在各种场景下都能稳定表现良好，而TA（可能是某种算法）仅在部分场景（如循环排序访问有效的场景）中表现出色。不过，在TA表现好的场景中，基于成本的方法也能有较好的表现，尽管它在解决方案搜索过程中会产生额外的开销。 #### 2. 天际线查询框架 ##### 2.1 基本定义 为了更好地理解天际线查询，我们需要先明确几个基本概念： - **支配关系（Dominance）**：给定 $p, q \in S$，如果对于所有的 $i \in [1, d]$ 都有 $p_i \leq q_i$，并且存在 $j \in [1, d]$ 使得 $p_j < q_j$，则称 $p$ 在 $D$ 上支配 $q$，记作 $p \prec_D q$。 - **不可比关系（Incomparability）**：给定 $p, q \in S$，如果 $p$ 不支配 $q$ 且 $q$ 也不支配 $p$，则称 $p$ 和 $q$ 在 $D$ 上不可比，记作 $p \sim_D q$。 - **天际线（Skyline）**：一个点 $p$ 是 $D$ 上的天际线点，当且仅当任何其他点 $q$（$q \neq p$）都不支配 $p$。给定数据集 $S$ 在 $D$ 上，天际线是一组天际线点的集合，即 $SKY_D(S) = \{p \in S | \nexists q \in S : q \prec_D p\}$。 为了后续使用，我们将支配和不可比的概念扩展到“区域级别”： - **区域级支配关系（Region - level dominance）**：给定两个区域 $R$ 和 $R'$ 在 $D$ 上，如果 $R$ 的虚拟最坏点 $R_w$ 支配 $R'$ 的虚拟最好点 $R'_b$，则称 $R$ 支配 $R'$。 - **区域级不可比关系（Region - level incomparability）**：给定两个区域 $R$ 和 $R'$ 在 $D$ 上，如果 $R$ 的虚拟最好点 $R_b$ 不支配 $R'$ 的虚拟最坏点 $R'_w$，且 $R'$ 的虚拟最好点 $R'_b$ 不支配 $R$ 的虚拟最坏点 $R_w$，则称 $R$ 和 $R'$ 不可比。 在上下文明确的情况下，我们会用 $\prec$、$\not\prec$、$\sim$ 和 $SKY(S)$ 分别代替 $\prec_D$、$\not\prec_D$、$\sim_D$ 和 $SKY_D(S)$。 对于排序查询，我们的目标是找到成本 $C$ 最小的最优算法。然而，天际线算法的成本函数与排序算法不同。排序算法通常只需要进行亚线性扫描和较低的计算成本，而天际线算法需要进行大量的成对支配测试。因此，天际线算法的成本函数 $C$ 通常是统计所执行的支配测试的数量。 ##### 2.2 现有算法的局限性 现有的天际线算法大多专注于减少点级别的支配测试，但不可比性也是优化天际线计算的另一个关键因素。在高维空间中，大多数点对都是不可比的。例如，在一个包含 200,000 个均匀分布且属性独立的合成数据集中，当维度较低时，几乎所有的点对都存在支配关系；而当维度高于 13 时，不可比的点对开始占主导地位。这表明，为了使天际线查询处理在维度上具有可扩展性，同时考虑支配和不可比性是至关重要的。 此外，平衡支配和不可比性并非易事。现有的工作大多通过选择一个能最大化支配区域的枢轴点来优化支配关系，而另一种极端情况是仅为了不可比性而选择一个能“均匀”划分整个区域的枢轴点，以最大化不可比子区域。但要在这两个极端之间找到一个成本最优的策略是非常困难的。 不过，基于成本的优化方法可以在成本函数的指导下平衡这两个因素。具体来说，区域级支配关系可以用于减少非天际线点的支配测试，而区域级不可比关系可以用于避免不可比点之间的支配测试，从而节省计算成本。 ##### 2.3 提取通用骨架 我们可以从一类现有的算法中提取出通用的骨架，其中有两个关键的通用模块：$SelectPivot()$ 和 $Prune()$。所有算法的共同优化目标是设计 $SelectPivot()$ 模块，以最小化 $Prune()$ 模块中的成本。由于支配测试是总成本的主要因素，我们的目标是开发一个能最小化 $Prune()$ 模块中支配测试数量的 $SelectPivot()$ 模块。 为了实现这个目标，我们定义了一个最优的 $Prune()$ 实现 $Opt$，它只需要进行最少的支配测试就能找到正确的天际线结果。具体的算法如下： ```python def Opt(pV, S): S = MapPointToRegion(pV, S) # 移除 S2d - 1 中被 pV 支配的所有点 S = S - Dominance(pV, S[2**d - 1]) B = [B0, ..., B[2**d - 2]] for (Bi, Bj) in B * B: # 检查部分支配关系，并移除被支配的点 if Bi ≺Par Bj and Si != []: S = S - Dominance(Si, Sj) elif Bi ∼ Bj: contin ```