Location Based Skyline Query Processing Technology On Road Network

With the development of geographic information positioning technology,LBS have been widely used in users’ lives.The main goal of the LBS system is to obtain the user’s location and provide the user with instant information for the user to make a decision.LBS has important application value in areas such as vehicle navigation,medical insurance,and user shopping.However,the traditional LBS only focuses on one dimension of the road network distance.For example,the traditional LBS can only find the closest hotel to the user but cannot find the hotel that is close to the user and has a low price.Skyline query is a multi-dimensional target optimization query,which is used to find a collection of all points in the database that are not dominated by other points,For example,find hotels with high ratings,close distances,and low prices.It plays an important role in finance,military,and urban transportation.Therefore,this article introduces static skyline query into the road network environment to solve the problem of users looking for hotels that are close and cheap,which is of great significance to solving users’ diversified services based on location.When performing skyline query processing in a road network environment,not only needs to consider the preference requirements given by the user,but also the user’s query location information and the location information of the Target tuples.However,there is no effective skyline algorithm in the existing road network.The calculation mechanism of road network distance causes the efficiency of existing road network skyline query algorithms to be relatively low.Aiming at the shortcomings of existing algorithms,this thesis studies efficient road network skyline query,the main research content is as follows:(1)Aiming at the location-based skyline query of the road network,a DSR algorithm(Dynamic Skyline Processing based on Road network)based on the inverted index of the management road network Target tuple and the G-tree index is proposed.The algorithm first proposes an inverted index structure based on road network Target tuples,which is used to manage the dimensions of road network Target tuples,and sort the Target tuples from good to bad according to the value of the Target tuples in each dimension.The index can be used to filter Target tuples that do not need to calculate the distance of the road network,and at the same time speed up the determination of the dominant relationship between the Target tuples.Secondly,an effective scanning strategy is adopted,which only calculates the road network distance of a small part of the Target tuples,and can efficiently determine the dominance relationship.Subsequently,when the target tuple is updated,the dynamic maintenance of the DSR algorithm is proposed.Finally,a large number of simulation experiments prove the effectiveness of the DSR algorithm.(2)Based on the DSR algorithm,the DSR~* algorithm is proposed.The algorithm first proposed a GD-tree index to speed up the calculation of the road network data distance.Secondly,considering that the calculation of non-spatial dimensions is easier than the calculation of spatial dimensions,this thesis proposes the concept of the optimal scanning end point,proposes a frequency statistical histogram for non-spatial dimensions,and proposes statistical closest and farthest distances for distance dimensions.Used to select the best scanning end point.Finally,the optimized scanning strategy is used to complete the calculation of the contour results.Finally,a large number of simulation experiments prove the effectiveness and efficiency of the DSR~* algorithm.