路网中位置不确定的二元反kNN查询

• 作者: 关佶红 张毅超 徐伟 李文根
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 反kNN查询 路网 Dijkstra算法 不确定性
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 第33届中国数据库学术会议(NDBC 2016)
• 页码范围: 341-346
• 页数: 6页
• 分类号: TP311.13|TP392
• 字数: 6335字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017.02.0341

摘要

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询(PBRkNN),旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值.为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率.最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐伟	同济大学计算机科学与技术系	227	1665	19.0	29.0
2	关佶红	同济大学计算机科学与技术系	50	522	13.0	21.0
3	李文根	同济大学计算机科学与技术系	3	2	1.0	1.0
4	张毅超	同济大学计算机科学与技术系	2	2	1.0	1.0