宽松反向最近邻查询算法解析与实验评估

### 宽松反向最近邻查询算法解析与实验评估 #### 1. 区间查询与算法概述 在处理相关数据时，我们用 $A_i.interval$ 表示从 $A_i.min$ 到 $A_i.max$ 的区间，$e.interval$ 表示从 $mindist(q, e)$ 到 $maxdist(q, e)$ 的区间。根据观察，如果条目 $e$ 能被 $A_i$ 修剪，那么 $e.interval$ 必须与 $A_i.interval$ 重叠。为了高效检索与 $e.interval$ 重叠的所有 $A_i$，我们使用区间树。对于每个分区 $P_i$，维护一个区间树 $T_i$，它包含与 $P_i$ 重叠的所有 $A_j \in A$ 的 $A_j.interval$。当检查与分区 $P_i$ 重叠的条目 $e$ 是否能被 $A$ 修剪时，在 $T_i$ 上以 $e.interval$ 为输入进行区间查询，将查询返回的所有区域 $A_j$ 组成的集合记为 $A_e$，在算法中使用 $A_e$ 代替 $A$。区间查询的成本为 $O(m + log n)$，其中 $n$ 是区间树中存储的区间数量，$m$ 是与输入区间重叠的区间数量。 #### 2. 算法流程 我们的算法主要由三个阶段组成，分别是修剪阶段、过滤阶段和验证阶段。 - **修剪阶段**：使用设施 R*-树修剪搜索空间，计算出修剪区域集合 $A$。具体操作步骤如下： ```plaintext Algorithm 2. Pruning Input: facility R*-tree, and a query q Output: The set of pruned areas A 1: A ← φ 2: insert root of facility R-tree in a h 3: while h is not empty do 4: de-heap an entry e 5: e′ ← PruneEntry(e, A) ▷ Algorithm 1 6: if e′ ≠ φ then ▷ e is not pruned 7: if e is an intermediate or leaf node then 8: for each side ab of e do 9: create Ai = Ca ∩ Cb and insert in A 10: for each child c of e do 11: if c overlaps with e′ then insert c in the heap 12: else ▷ e is a facility point 13: create Ai = Ce and insert in A ``` 该算法首先初始化一个堆 $h$，将设施 R*-树的根节点插入堆中。然后不断从堆中取出条目进行处理，如果取出的条目 $e$ 能被修剪（即 $e'$ 为空），则忽略它；否则，若 $e$ 是中间节点或叶子节点，为其每一侧创建修剪区域 $A_i$ 并插入 $A$ 中，同时将与 $e'$ 重叠的子节点插入堆中；若 $e$ 是设施点，则创建修剪圆 $C_e$ 并添加到 $A$ 中，直到堆为空。 - **过滤阶段**：对位于修剪空间内的用户进行修剪，将剩余用户插入候选列表 $L_{cnd}$。具体操作步骤如下： ```plaintext Algorithm 3. Filtering Input: user R*-tree, query q, and A Output: a list of candidates Lcnd 1: Lcnd ← φ 2: insert root of user R*-tree in a stack S 3: while S is not empty do 4: retrieve top entry e from S 5: e′ ← PruneEntry(e, A) ▷ Algorithm 1 6: if e′ ≠ φ then ▷ e is not pruned 7: if e is an intermediate or leaf node then 8: for each child c of e do 9: if c overlaps with e′ then insert c in stack S 10: else ▷ e is a user 11: insert e in Lcnd ``` 该算法初始化一个栈 $S$，将用户 R*-树的根节点插入栈中。不断从栈中取出条目 $e$ 进行处理，如果 $e$ 能被修剪，则忽略它；否则，若 $e$ 是中间节点或叶子节点，将与 $e'$ 重叠的子节点插入栈中；若 $e$ 是用户，则将其插入候选列表 $L_{cnd}$，直到栈为空。 - **验证阶段**：对候选列表 $L_{cnd}$ 中的每个候选用户 $u$ 进行验证，判断其是否为查询 $q$ 的宽松反向最近邻（RRNN）。具体操作是，以用户 $u$ 为中心，$r = \frac{dist(u,q)}{x}$ 为半径进行圆形布尔范围查询，若查询结果为假，则将 $u$ 作为答案报告。 #### 3. 实验设置 由于之前没有解决 RRNN 查询的算法，我们考虑了一个简单算法（RQ），并努力设计了一个改进版本（IRQ）。 - **范围查询（RQ）**：对于每个用户 $u$，在设施 R*-树上以 $dist(u, q)/x$ 为范围进行布尔范围查询。 - **改进的范围查询（IRQ）**：如果用户 R*-树的中间节点或叶子节点条目 $e_u$ 满足存在至少一个设施 $f$ 使得 $mindist(e_u, q) > x × maxdist(e_u, f)$，则该条目不能包含任