不确定向量空间中的概率排序

### 不确定向量空间中的概率排序 #### 1. 引言 在处理不确定数据时，概率最近邻查询的高效计算一直是研究的重点。以往的方法虽能实现概率最近邻查询的高效计算，但大多仅支持单最近邻查询。对于 k - 近邻查询，其主要挑战在于对象的邻域概率依赖于数据库中的其他对象。 近期，有研究提出了关系数据库中不确定数据的 top - k 查询处理算法，包括不确定 top - k 查询（U - Topk）和不确定 k 排名查询（U - kRanks）。不过，这些方法与我们要解决的问题在模型定义上有所不同。本文旨在为概率排序查询提供高效的解决方案，结果将按排序参数 k 的升序迭代报告。我们假设不确定对象由向量空间中的一组点表示，这使得我们能够使用标准的空间访问方法（如 R∗ - 树）来高效组织不确定对象，并利用标准的相似性搜索范式来支持概率排序。 #### 2. 问题定义 ##### 2.1 位置不确定对象 在 d 维向量空间 $R^d$ 中，如果对象没有唯一的位置，而是有多个与概率值相关联的位置，则称这些对象为位置不确定对象。具体定义如下： 设 D 是位于 d 维特征空间 $R^d$ 中的对象数据库。对应离散不确定性模型，不确定对象 o 由 d 维向量空间中的一组有限的替代位置表示，每个位置都关联一个置信值，即 $o = \{(x, p) : x \in R^d, p \in [0, 1], p$ 是 x 为对象 o 的位置的概率 $\}$。置信值 p 表示向量位置与对象 o 对应位置匹配的可能性，且满足 $\sum_{(x,p) \in o} p = 1$。 ##### 2.2 不确定对象的距离计算 位置不确定对象之间的距离也是不确定的。对于离散不确定性表示的不确定对象，我们需要一种特殊的距离定义。 设 $dist : R^d × R^d → R^+_0$ 是基于 Lp 范数的相似性距离函数，$o_i \in D$ 和 $o_j \in D$ 是两个相互独立的不确定对象。则离散不确定性模型中的不确定距离是一个集合： $d_{uncertain}(o_i, o_j) = \{(d, p) \in R^+_0 : \forall(x, p_x) \in o_i, \forall(y, p_y) \in o_j : d = dist(x, y), p = p_x · p_y\}$，且满足 $\sum_{(x,p) \in d_{uncertain}(o_i,o_j)} p = 1$。 两个不确定对象 $o_i$ 和 $o_j$ 之间的不确定距离小于给定范围 $\epsilon \in R^+_0$ 的概率可以通过以下公式估计： $P(d_{uncertain}(o_i, o_j) \leq \epsilon) = \sum_{(x, p) \in d_{uncertain}(o_i, o_j), d \leq \epsilon} p$ 由于不确定对象之间的距离计算成本很高，我们引入了距离近似方法，包括最小对象距离和最大对象距离： 设 $o_i = \{o_{i,1}, o_{i,2}, .., o_{i,M}\}$ 和 $o_j = \{o_{j,1}, o_{j,2}, .., o_{j,M'}\}$ 是两个不确定对象。 最小距离：$d_{min}(o_i, o_j) = min_{s = 1..M, s' = 1..M'}\{dist(o_{i,s}, o_{j,s'})\}$ 最大距离：$d_{max}(o_i, o_j) = max_{s = 1..M, s' = 1..M'}\{dist(o_{i,s}, o_{j,s'})\}$ ##### 2.3 不确定对象的概率排序 概率查询的输出通常是一组结果对象，每个对象都关联一个概率值，表示该对象满足查询谓词的可能性。与 ε - 范围查询和 k - nn 查询不同，排序查询没有唯一的查询谓词，因为查询谓词会随每个排序位置而变化。在排序查询中，每个结果对象会被分配一组概率值，每个排序位置对应一个概率值，我们称这种排序输出形式为概率排序。 设 q 是一个不确定查询对象，D 是包含 $N = |D|$ 个不确定对象的数据库。不确定排序是一个函数 $prob\_ranked_q : (D × \{1, .., N\}) → [0..1]$，它报告数据库对象 $o \in D$ 在排序位置 $k \in \{1, .., N\}$ 的概率，该概率反映了根据 $o$ 与查询对象 $q$ 之间的不确定距离 $d_{uncertain}(o, q)$ 按升序排列时，$o$ 处于第 $k$ 个排序位置的可能性。 为了方便用户获取相关信息，我们定义了不同类型的概率排序查询，具体如下： - **基于最大置信度的概率排序查询（PRQ MC）**：该查询按顺序报告对象，使得第 k 个报告的对象在给定排序位置 k 具有最高的置信度。具体来说，对于下一个排序位置 $i \in N$，它会检索形式为 $(o, prob\_ranked_q(o, i))$ 的结果元组，其中 $o \in D$ 未在之前的排序迭代中报告过，并且对于所有未在之前排序迭代中报告过的 $p \in D$，有 $prob\_ranked_q(o, i) \geq prob\_ranked_q(p, i)$。 - **基于最大聚合置信度的概率排序查询（PRQ MAC）**：此查询考虑了排序位置的聚合置信度。对于下一个排序位置 $i \in N$，它会检索形式为 $(o, \sum_{j = 1..i} prob\_ranked_q(o, j))$ 的结果元组，其中 $o \in D$ 未在之前的排