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

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