Abstract: According to the shortage that the existing method cannot handle the obstacle k aggregate nearest neighbor queries on uncertain data, this paper proposes a probabilistic obstacle [k] aggregate nearest neighbor query (POkANN) method based on the uncertain Voronoi diagram. The method consists of three phases, which are processing, pruning and refining. The processing phase is to process the minimum covered circle of the query points set which is prepared for the pruning phase. Different pruning algorithms are proposed for three aggregate functions in pruning phase. The data points that must not be the answer are pruned and the candidate set is obtained. In refining phase, the preceding k data points in the candidate set whose probabilities are greater than the given threshold are stored into the result set and return to the user. The theoretical results and experimental results show that the method proposed in this paper has obvious advantages on probabilistic obstacle k aggregate nearest neighbor queries.

Key words: uncertain data, uncertain Voronoi diagram, obstacle, k aggregate nearest neighbor

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

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