Design And Implementation Of Uncertain Data Neighbor Search Algorithm

Data uncertainty is prevalent and exists in applications of many fields. Uncertaindata has received increasing attention. The reasons why uncertain data are produced arevarious. Raw data’ imprecision or using group granularity will lead to uncertainty in thedata collection. In addition, a special purpose for privacy protection and handlingmissing data values may be the reasons for the uncertainty. How to deal withuncertainties in the data really become a hot issue in recent years in the field of databaseresearch.In this paper, we study the nearest neighbor queries processing algorithms for theuncertain data. The introduction of data uncertainty leads to the improper of traditionalmethods. So traditional methods is not directly applicable to query processing onuncertain data. And this paper gives the solutions of group reverse k nearest neighborquery and predictive nearest neighbor query on uncertain data.Reverse k nearest neighbor query plays an important role in location-based servicesto evaluate the influence of objects. Currently, most of methods for the reverse k nearestneighbor query only consider the single query point. Therefore, in this paper, wepropose the probabilistic threshold group reverse k nearest neighbor query processingalgorithm (PT-GRkNN) for uncertain data to evaluate the influence of a group of objects.PT-GRkNN uses R*-tree index structures, filtering-refinement frame to reduce thequery search space and improve efficiency of searching. The experiments results showthat PT-GRkNN can reduce the search space, accurately filter out non-result set objectsand improve the accuracy of the results.Predictive nearest neighbor queries over spatial-temporal data have receivedsignificant attention in many location-based services including intelligent transport, ridesharing and advertising. Due to physical and resource limitations of data collection devices like RFID, sensors and GPS, data are collected only at discrete points of time.In-between these discrete time instances, the position of tracked moving objects areuncertain. In this paper, we exploit the filter and refine framework to solve thepredictive nearest neighbor queries over uncertain spatial-temporal data. Specifically, inthe filter phase, our approach employs a semi-Markov process model that describesobjects mobility between space grids and prunes those objects that have zero probabilityto encounter the query object. In the refine phase, we use a Markov chain model todescribe the mobility of moving objects between space points and compute the nearestneighbor probability for each candidate objects. We experimentally show that ourapproach accelerates the existing index-based approach by orders of magnitude.