路网中位置不确定的二元反kNN查询
来源：计算机应用杂志2017年第2期北京时间：
作者：徐伟, 李文根, 张毅超, 关佶红
单位：同济大学 计算机科学与技术系, 上海 201804
摘要：针对路网限制和物体位置的不确定性，提出了路网中位置不确定的二元反kNN查询（PBRkNN），旨在查找一组位置不确定的点，使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题，首先提出一种基于Dijkstra进行剪枝处理的基本算法，即PE算法；接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度，即PPE算法；而为了进一步减小PPE算法中范围查询的开销，提出PPEE算法，利用网格索引来索引范围查询中要查询的不确定空间点，从而提升算法的效率。最后，在北京和加州路网数据集上进行了大量实验，结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。
关键词：反kNN查询,路网,Dijkstra算法,不确定性
基金资助：国家自然科学基金资助项目（61373036）；上海市优秀学术带头人计划项目（15XD1503600）。
