面向不确定数据的概率障碍k聚集最近邻查询

来源：计算机科学与探索杂志2018年第2期北京时间：

作者：于嘉希，李松，张丽平，刘蕾

单位：哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

摘要：针对现有方法无法有效处理不确定数据的障碍[k]聚集最近邻查询问题的不足，提出了基于不确定Voronoi图的概率障碍k聚集最近邻查询（probabilistic obstacle k aggregate nearest neighbor query，POkANN）方法。该方法分为3个阶段，分别是查询点集处理阶段、过滤阶段和精炼阶段。在处理阶段，计算查询点集的最小覆盖圆圆心q，为剪枝做准备。过滤阶段针对3种聚集函数设计了不同的过滤算法，去除不可能成为结果的数据点进而得到候选集合。精炼阶段将候选集合中概率值大于给定阈值的k个数据点集合存入结果集合并返回给用户。理论研究和实验表明，所提出的方法在概率障碍[k]聚集最近邻查询方面有明显的优势。

关键词：不确定数据,不确定Voronoi图,障碍,k聚集最近邻