路网中基于预计算的跳跃式查询最近邻的算法

• 作者: 王恒
• 来源期刊: 天津理工大学学报
• 学科: 工学
• 关键词: 空间网络数据库 最近邻查询 基于位置的服务 UNICONS 跳跃式查询
• 年，卷（期）: 2011,（2）
• 页码范围: 38-42
• 分类号: TP311
• 字数: 3318字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-095X.2011.02.009

摘要

在空间网络数据库(SNDB)中,最近邻查询(NN)在基于位置的服务(LBS)中尤为关键.现有的查询处理方法大多依赖于路网的稀疏程度,其他处理方法如UNCONS等改进了该不足,但可能存在过计算的问题.针对后者,本文提出并证明了基于非交叉点路径中的预计算理论,同时基于该理论提出一种通用的基于SNDB的NN查询处理方法,该方法通过跳跃式查询交叉点的最近邻来降低预计算的代价.通过实验,验证了本文提出的处理方法在最近邻查询中的正确性和有效性,特别是在交叉点分布稀疏的路径上,性能优势尤为明显.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王恒	天津理工大学计算机与通信工程学院	3	8	2.0	2.0