道路网络中k路径最近邻居针对两种目标点的应用.pdf

小 型 微 型 计 算 机 系 统 年 月 第 期
． ．
道 路 网络 中 路 径 最 近 邻 居 针 对 两 种 目标 点 的应 用
宋海涛 ，张守志 ，施伯乐
复旦大学 计算机科学技术学院 ，上海
—： ．．
摘 要 ：提 出一种道路 网络 中针对 两种 不同类型 目标 点的 组路 径最近邻居查询 ，这是 一种新的查询 ：给 出用户希 望到 达的终
点位 置以及 两组 目标点集合 ，这种查询返 回连接 用户 当前位 置和终点位置的最短路径 ，以及 相对于这条最短路 径的 组路径最
近 邻居 ，每组 包含 两个 不同类型 的 目标 点 ，将这种查询命名 为 —．提 出了一 种典型 的过 滤·精 炼算 法得 到 —及 对应
的最短路 径 ，并且在 实际道路 网络 中进行 了实验．实验证 明，算法可行 ，有 效．
关 键 词 ：路径最近邻居 ；两类 目标 点 ；道路 网络 ；过滤精炼
中图分类号 ： 文献标识码 ： 文 章 编 号：——

—，—，—
，。，
：，：
，
，—，—．——
。 ．。
．
：；；；—
概 述 最 优序列 问题．
我们 注意到 ，在上 述 — 中 目标 点 的类 型只有 一种 ，
最近邻居 问题 是空 间数据库研 究领域最 基本 的 但在某些情况下 ，可能在 一次查 询 中存 在用户感 兴趣 的两种
问题 之一 ，是指在特定空 间 中寻 找离查询 点最近