The Research On Methods For Group Nearest Neighbors Query On Uncertain Data

The popularity of mobile devices makes the query service of the spatial location have gradually gone deep into people's lives.Meanwhile attract a large number of researchers to study the issue.While because of the error of data collection and measuring equipment,delayed data update or privacy protection leads to the phenomenon that uncertain data are prevalently inherent in many various applications.Currently,many kinds of queries on certain data have been studied maturely,but the methods for processing the queries on uncertain data are still not perfect.Therefore,this article carries on research for the issue of group nearest neighbor query on uncertain data.Group nearest neighbor query on uncertain data is probabilistic group nearest neighbor(PGNN)query.PGNN query needs to find all the uncertain objects whose probabilities of being GNN results are not less than a user-specified threshold.Currently,the research of PGNN query is not so much and the research is mainly carried on under the European space.However the existing algorithms of PGNN query have several problems,such as large retrieval range and distance calculations redundant.For these shortcomings,this article proposes an algorithm based on Voronoi diagram of PGNN query.Firstly,we analyze some characteristics of Voronoi diagram and combine with the convex hull of query set to construct an influence zone for determining the candidate set of query results.And the corresponding algorithm is given.Then we use the space pruning algorithm to reduce the above candidate set,which reduce the retrieval space and distance calculation greatly.Next we give the computational formula of probabilities of uncertain objects of being GNN query results.And the formula is used in a little number of uncertain objects who cann't be pruned in the phase of space pruning.Then in view of the large amount of query points and further improving the query efficiency,this article also proposes an algorithm of using uncertain Voronoi diagram to process quickly PGNN query.Firstly,we group the query points by following the principle of grouping.Then combine the character of uncertain Voronoi diagram with the convex hull of new query points to build the candidate set,which can reduce the number of candidate objects.At last,we prune the candidate set using space pruning algorithm and compute the probability of objects which can't be pruned being GNN result.At last,we use synthetic dataset to do comparative experiments under several different parameter values.The experimental results show that the algorithm based on Voronoi diagram is more efficient than the existing algorithm on the query time.And algorithm UVPGNN is more efficient than VPGNN when the number of query points is large and the query needs to get the results as soon as possible.