In order to solve the problem of probabilistic group nearest neighbor query on uncertain data, we present an effective method based on Voronoi diagram. Probabilistic group nearest neighbor query on uncertain data is to find out the set of uncertain objects, in which each object has a higher probability to be the nearest neighbor of query set than the threshold specified by user. In this paper, first a candidate set of target objects is got by constructing the Voronoi diagram of uncertain objects and the convex hull of the set of the query points. Then further reduce the candidate set through using the space pruning algorithm. At last, calculate the probability value of each target object in the candidate set to be GNN result exactly. The uncertain objects whose probabilities greater than or equal to the user-specified threshold are put into the result set. The theoretical analysis and experiments show the effectiveness of our algorithm, which also has good performance and less query time.
['Weige Wang', 'Jian Xu', 'Ming Xu', 'Ning Zheng', 'Enquan Ge']
Probabilistic Group Nearest Neighbors query based on Voronoi diagram