Abstract
The skyline query is useful to users, which helps them make decisions from lots of choices. The traditional skyline query was addressed considering a data space where all dimensions of a data point are static. For example, the distance to the beach of a hotel is static. However, some attributes of a data point may be dynamic. For example, the distance to the beach of a moving car is dynamic, depending on the location of the car. The spatial skyline query to be addressed in this paper considers a data space where some dimensions of a data point are dynamic. Consider a scenario as follows. The route of a moving vehicle can be considered as a series of line segments. A user on the route may issue a skyline query to find restaurants taking into account the static attributes of the restaurants as well as the distance to them. In this paper, we focus on a new skyline query named continuous spatial skyline query over a line segmaent.as described in the following. Given a data set D, a query line segment l (to describe a part of the route), and a distance of r (to describe the acceptable distance for users’ access) in a two-dimensional space, the skyline query retrieves corresponding skyline points within the distance constraint r in each sub-segment of l. We propose two methods to solve the problem. In the basic method, we find some intersection points which may change the skyline results and compute the skyline on these points. In the pruning method, we propose properties to prune some data points for reducing the skyline computation cost. Since many sub-segments can be produced, in order to reduce the number of sub-segments, we also propose an approximate method, and define a similarity function to measure the similarity between the exact result and the approximate result. We perform experiments to evaluate the two methods and the results show that the pruning method is more efficient than the basic method. Moreover, we perform experiments to compare the exact results and approximate results and it shows that there is a trade-off between the reduction of sub-segments and the accuracy of the results.