Research On Probabilistic Aggregate Nearest Neighbor Query Method Over Uncertain Data

The query problem of spatial data has widespread application value in Geographic Information System,location-based services and other fields.The nearest neighbor query is a fundamental problem.This problem finds the data point which has the smallest distance from the query points by compute the distance between the data point and the given query points.To satisfy the different query requirements,the nearest neighbor query problem has been expended.The aggregate nearest neighbor query is to find the point which has the smallest aggregate distance from the given query point set and become the research emphases in resent years.The traditional aggregate nearest neighbor query is dealing with the accurate data.But for the reasons of inaccurate and incomplete raw data,dealing with the missing data,data conversions,and so on,the uncertainty has been introduced into the traditional spatial data.The uncertain data has become a hot issue in the current research gradually.However,the traditional method cannot be applied to the uncertain data directly.Accordingly,this paper research the related issues of aggregate nearest neighbor query based on uncertain Voronoi diagram.The main research content of this paper is as follows:Firstly,this paper researches the probabilistic threshold group k nearest neighbor(PTGk NN)query over uncertain data.PTGk NN qurery is the sum function of aggregate nearest neighbor query,which is specially discussed because of its wide application.Since the particularity of uncertaint data,massive probability-value calculations are involved by the nearest neighbor query over it which becomes the major factor of CPU time.To avoid the probability-value calculation of invalid data,the PTGk NN method is proposed in this paper.Use the property of uncertain Voronoi diagram to filter part of the data points,anddesign the corresponding pruning strategic according to the query problem to get the calculate set which can reduce the probability-value computation of the result set effectively.This paper further study the problem of probabilistic threshold aggregate nearest neighbor query problem over uncertain data.The PTANN method is proposed.The corresponding pruning strategies are designed according to the three kinds of aggregate function.The effect on the original query result by adding or removing the data points is also discussed.At last,the probabilistic threshold obstacle k aggregate nearest neighbor query over uncertain data is studied,which resolve the problem of obstacle.The calculation method of obstacle aggregate distance is proposed.In this paper,we proposed the PTOk ANN method which returns the k data points that have the smallest obstacle aggregate distance from query data set.The pruning strategies are designed by different aggregate function with obstacle which the meet the needs of practical applications.This method also designs the different pruning strategies in different circumstances with the obstacle which can prune the data points that cannot be the result effectively.