Research On Probabilistic Skyline Query Processing Over Uncertain Moving Objects

With the rapid development of information technology,all kinds of uncertain data query have been widely used in many popular applications.Recently,as the use of handheld wireless terminals and vehicle equipments with position function are getting more and more widespread,the demand for location-based mobile computing is pressing.The skyline query returns a set of data points that have an advantage over the other data points referring to the query object.However,due to the constraint of the limitation of hardware devices,update delay,network bandwidth and so on,the location information of the mobile objects tends to be uncertain,which may affect the calculating of skylineresults.The probabilistic skyline query considers the motion ofquery objects,and returns the data which are most likely to have the advantage.In this thesis,the probabilistic skyline query processing techniques for uncertain mobile objects in road networks and general cases are studied.The main work and innovations are listed as follows:(1)Continuous probabilistic skyline query of moving data points in Manhattan road network is studied.Considering uncertain continuous mobility of the target data points in the road network environment,this thesis mainly studies the problem of continuous probabilistic skyline query for uncertain mobile data points in Manhattan road networks.The interest points in the road network are regarded as moving target data points and have the uncertainty which is consistent with the description of the probability density function.First of all,according to the initial position of the target data points as well as the static properties,the initial skyline results are retrieved.Then,according to the dominating relationship among mobile data points,events for maintainingskyline results in future are predicted.Finally,update probability skyline resultsaccording to the sequence of obtained events,so as to realize the continuous probabilistic skyline query processing.(2)The calculation method of dominance probability based on geometric probability model isproposed.According to the environment of uncertain moving objects as well as their characteristics,the classification and modeling for uncertain moving objects are studied.Considering the two basic requirements of geometric probability models: infinite" and "possibility",moving objects are transformed and modeledwith geometric probability models.We improve the dominance checking between uncertain moving objects by transferringthe problem into thecalculation of "measure"(e.g.,length,area or volume),intuitively,which can greatly accelerate the skyline query processing.(3)We look into the problem of probabilistic skyline query for uncertain moving objects based on Manhattan distance.First of all,by utilizing probability calculation models based on Manhattan distance,the skyline results at time tthat objects with a skyline probability larger than p,called p-t-skyline,isobtained.Considering that the computation of skyline probability for a large number of uncertain moving objects is very expensive in real applications,this thesis proposes a solution which includes four steps: sampling,restriction,pruning and refining.Besides,a multi-dimensional index structure VCI-tree is adopted to improve the efficiency of data retrieval.Experimental results show that the solution has good performance in different data size and dimension data set.