Research On Skyline Query Processingin Road Networks

With the development of information technology, people’s ability to obtain information is gradually stepping up. The amount of information increases sharply and the form is gradually diversified, which also make an increasing requirement for the storage capacity and processing technology of databases. As a result of that, skyline queries attract people’s attention as a database operation which can make multi-criteria optimization among multi-attribute data sets. The skyline queries can help users get useful information messages from huge amounts of data to make right decisions. That has very important application value in different fields such as location-based services(LBS), stock recommendations and environment monitoring.Most of the existing skyline query technology for LBS limit for the Euclidean space, but in the actual LBS applications, most objects we concerned are located in a confined space, especially the road networks. Due to that the existing algorithms failed to accurately consider the effect of the specific road structure, as well as the connections between the objects’ non-spatialel and spatial domination rationships in road networks,their efficiency and precision are low in practical application. In this thesis, we propose efficient skyline query algorithms for several scenarios in road networks. The mian research work and contributions are summarized as follows:(1) We study a new problem of range-based skyline query in road networks for the consideration of user privacy and the limited accuracy of positioning devices. We first propose a basic algorithm which converts the problem to nomal point-based skyline query based on a boundary substitution theorem. In addition, we introduce the Voronoi cell of road network and create a road domination model. We design an index structure to index the skyline objects in the road networks based on the model. The new index-based algorithm we proposed effectively improves the efficiency and precision of the query.(2) We study the continuous K nearest neighbor-skyline(KNN-skyline) query problem which can retrieve the k nearest skyline objects for a moving query point in road networks. An algorithm based on safe region is proposed in this thesis. The safe region for skyline set and the fixed rank region for KNN are first brought to constitute the complex safe region and maintain the result set. Only when the query point reaches a certain boundary point of the regions, an update for the result set and safe regions will be triggered in the algorithm, which greatly improves the efficiency by avoiding repeated computation of snapshot queries of the continuous query.(3) We study a problem of continuous skyline query for moving objects in road networks. We propose an event-based incremental processing algorithm. Firstly, we establish explicit data models for the items in road networks. Then we realize the query on the strength of tracking dominant relationships between objects with the distances changing and finding the result changing points. Meanwhile, some pruning strategies are adopted to prune the events which have no effects on the results to improve the efficiency of the algorithm.