一种障碍空间数据库中的连续反k近邻查询方法-论文.pdf

谷峪 等：一种障碍空间数据库中的连续反 近邻查询方法
近年 来，随着 智能移动 设备 的快速 发展，基于 位置服 务技术 得到 了广泛 的应用 ．空 间数据库 作为重 要 的支 撑
技术 ¨】，为各类 位置相 关 的查询请求 ，例 如 近 邻查询 】、查询和 反 近 邻查询 等提供 了高效 的
数据 获取 服务．特 别地 ，在这些 查询 中，反 近 邻查 询用来搜 索那些 近邻 里面包含 查询 点 辞的空 问数据 点，从 而
反 映 了查询 点对 哪些 空间数 据 点影 响较大 ，被 证 实在空 间 决策支 持 、资源 分配和 数据 挖掘 方面有 着广 泛 的应
用．然而，之前 的大多 数空 间查询工作 往往考 虑理想 的欧式 空间和 路 网空 间．实际上，地面 、室 内甚至虚拟 空 间内
移动 的物体一般 都会受 到地理条 件 的限制例如建筑 、湖泊 等，因此，准确 的距 离计算需要考 虑障碍物 的因素．
在 各类 空间查询 中，连 续 的反 近邻 查询是 一类相对 复杂 的查询，可 以支 持高级 的分析和 预测应用 ．例 如，在
地 震 的救灾重 建工 作 中，需要在 灾 区设置 医疗和餐 饮安置 点，如果用 户驾驶 一辆载 满配送 药物和 食物 的车 ，查询
从 出发 点 到终 止点 的路 线上 ，可 以配 送给 哪些 安置 点 药物和 食物 ．显 然，这 些安 置点 需要距 离 查询线 段 比较近 ，
也 就是在 安置 点的 近 邻范 围 内否则，可 以从 其他 安置 点搬 运物 品，从而为优 化配送做 决策支 持．类似 的查 询
可 以支持 冰 山碰撞 预测 、野生 动物 领袖 发现和 虚拟游 戏伙 伴邀请 等 应用场 景．而在这 些空 间中，障碍物 都是 广
泛 存在的，准确地 计算 需要考虑 障碍物 的影 响．从上 面 的例 子可 以看 出：给定 一个轨迹 作为查询 区 间，连续 反 近
邻 问题 即连 续地给 出查询 点在 区间 内的反 近邻 数据对象 ．因为移动对 象在 查询区 间上的反 近 邻是分 段变化
的，因此该 问题 即转化 为对查 询区 问进 行合理 的分割，使 得每个 分割 的区问具有相 同的反 近邻 查询结果 ．
本 文针对 障碍 空问数据 库 中的连续 反 近 邻查询进 行研 究，引入 了控 制点和 分割点 的概念，提 出了剪枝数
据 集 、获取 障碍 物 、剪 枝和计算 控制 点和更 新结果集 的一套 高效处 理策略 ，从而 给 出了障碍空 间数据库 中的连
续反 近邻 查询的解 决方法 ．
本 文第 节 介绍相 关工作 ．第 节定义 障碍空 间的连续 查询和相 关概念 ．第 节 详细描述 障碍 空间
中连续 查询 的处理过 程，阐述 剪枝和 求精 的方 法．第 节给 出实验结果 以及分析