天际线查询及帕累托集选择策略

### 天际线查询及帕累托集选择策略 在数据处理和分析领域，天际线查询和从帕累托集中进行选择是重要的研究方向。本文将介绍天际线查询相关的多种概念和方法，包括 k - 优势天际线、天际线的总结方法以及对天际线点进行加权的策略。 #### 1. k - 优势天际线 k - 优势天际线的概念基于 k - 优势度量。若对象 $o_1$ 在至少 $k\leq d$ 个维度上优于或等于对象 $o_2$，且在这 $k$ 个维度中至少有一个维度上严格优于 $o_2$，则称 $o_1$ 对 $o_2$ 具有 k - 优势。帕累托天际线是 $k = d$ 时的 k - 优势天际线。 随着维度数量的增加，一个对象在所有维度上都比另一个对象差或相等的可能性变得极低。因此，k - 优势天际线允许属性值较少的对象被属性值较多的对象所支配。通过减小用户指定的 $k$ 值，得到的 k - 天际线的规模会减小，且较小 $k$ 值的 k - 天际线是较大 $k$ 值的 k - 天际线的子集，所有 k - 天际线都是原始天际线的子集。计算 k - 优势天际线需要专门的算法。 #### 2. 天际线的总结方法 为了让用户快速了解天际线结果集的性质和内容，便于进一步细化偏好或进行后续查询，需要对天际线进行总结。主要有以下两种方法： ##### 2.1 近似支配代表（ADR） ADR 是天际线查询的后续细化技术，旨在通过最优样本在大小和准确性方面覆盖整个天际线。ADR 查询返回一组 $k$ 个对象（$k$ 由用户指定），对于任意不在该集合中的对象 $a$，存在集合中的对象 $a_i$，使得向量 $a_i\cdot(1 + \epsilon)$ 支配 $a$。 ADR 是在实际天际线计算之后的步骤，因此无法获得性能优势，因为仍需计算完整的天际线。对于二维属性，找到最小的 ADR 具有线性时间复杂度，但对于超过二维的情况，该问题是 NP 难的。因此，开发了多项式时间的近似算法，但会牺牲一定的覆盖准确性。 ##### 2.2 统计采样天际线 统计采样天际线旨在返回原始天际线的代表性子集，特别适用于协作检索场景，并为后续的示例查询交互做准备。与 ADR 相比，该方法更注重计算性能，而对返回样本的准确性和代表性要求相对较低。 用户工作流程如下： 1. 使用采样天际线算法从数据库中快速生成样本集，该样本集应代表数据库中根据某些属性偏好最有趣的对象。 2. 获取用户对样本中偏好对象的反馈。 3. 发现所选对象的共同特征，例如推导 top - k 效用函数。 4. 向用户返回数据库中最佳对象的排序列表。 该算法基于计算 $q$ 个随机选择的 $m < n$ 维子空间的天际线，然后进行汇总。每个子空间天际线代表一个“感兴趣的主题”，且计算速度比完整天际线快得多。通过生成去重的子空间天际线的并集，可获得具有统计代表性的样本。 #### 3. 天际线点的加权特征 前面的方法主要关注覆盖天际线对象的多样性，而以下方法则根据明确建模的“有趣性”度量来选择和排名天际线的子集。 ##### 3.1 天际立方体和子空间分析 天际立方体包含给定数据集所有子空间（最多 $2^d - 1$ 个）的预计算非空天际线，类似于数据仓库中使用的数据立方体。通过预计算这些天际线，可以快速有效地回答钻取分析或子空间天际线成员查询。 计算所有子空间天际线主要有两种方法：自下而上和自上而下。自上而下的方法在计算过程中可以重用高维子空间天际线的结果，因此比自下而上的方法更高效，能使计算整个天际立方体的速度比单独计算所有子空间天际线快两个数量级。 天际线频率是一种用于对天际线对象进行排名和选择的指标，它计算每个天际线对象在所有可能的非空子空间天际线中出现的次数。出现频率较高的天际线对象被认为对用户更有趣。可以使用天际线频率为用户提供 $k$ 个最“有趣”的天际线对象的排序列表。 ##### 3.2 SKYRANK 算法 SKYRANK 算法基于天际线对象在子空间中的支配关系对其进行排名。其核心启发式规则如下： - 若一个天际线对象在不同子空间中支配许多其他重要的天际线点，则该对象更有趣。 - 一个天际线对象的有趣性会传播到在任何子空间中支配它的所有天际线对象。 为了计算这种递归的有趣性概念，SKYRANK 依赖于天际线图。天际线图的节点是全数据空间的所有天际线对象，边的构建基于数据集的天际立方体。对于全空间的每个天际线对象，检查其是否属于每个子空间的天际线，若不属于，则添加从该对象到支配它的对象的有向边。 SKYRANK 使用类似于 PageRank 的链接分析算法计算每个天际线对象的得分，这些得分可用于选择 $k$ 个最有趣的天际线对象的排序列表。该算法还可以通过为所有涉及的子空间提供 top - k 风格的权重进行个性化设置。 ##### 3.3 k 个最具代表性的天际线点（RSP） RSP 方法通过使用 $k$ 个最具代表性的天际线点来总结天际线。“代表性”的概念由对象支配的对象数量来定义，即一个天际线点支配的对象越多，它就越具代