Abstract
Skyline queries may be used to filter interesting data from a broad range of data. A Skyline query selects those data that are the best according to multiple user-defined criteria. A special case of Skyline queries are the Spatial Skyline Queries (SSQ). SSQ allow users to express preferences on the closeness between a set of data points and a set of query points. We study the problem of answering SSQ in presence of changing data, i.e., data whose values regularly change over a period of time. In this chapter, it is proposed an algorithm to evaluate SSQ on changing data. The proposed algorithm is able to avoid recomputation of the whole Skyline with each update on the data. Also, the performance of the proposed algorithm against state-of-the-art algorithms was empirically studied. The experimental study shows that the proposed algorithm may become 3 times faster than state-of-the-art algorithms.
TopIntroduction
Skyline queries are particularly relevant in the area of decision support or data visualization. They may be used to filter interesting data from a broad range of data. Intuitively, a Skyline query selects those data that are the best according to multiple user's criteria; user's criteria consist of minimizing or maximizing the attributes of an input dataset simultaneously.
A special case of Skyline queries is the Spatial Skyline Queries (SSQ); SSQ focus on geometric or spatial data and they allow expressing preferences on the closeness between a set of data points and a set of query points (Sharifzadeh & Shahabi, 2006).
The Skyline query evaluation is a costly process for a large dataset. The worst case complexity is 
where P is the dataset (Godfrey, Shipley, & Gryz, 2005). Clearly, the Spatial Skyline query evaluation is still more expensive because distance functions must be computed. In this sense, performing an exhaustive search increases the search space to 
where Q is the set of query points (Sharifzadeh & Shahabi, 2006). Sharifzadeh and Shahabi (2006) exploit geometric properties in order to reduce the search space to
, where S is the Skyline set and C is the vertex set belonging to the convex hull of the query points in Q. The convex hull of Q is the unique smallest convex polytope which contains all the points in Q (Sharifzadeh & Shahabi, 2006).
In this chapter, we study the problem of answering Spatial Skyline Queries (SSQ) in presence of both spatial and non-spatial changing data. Changing data are data whose values regularly change over a period of time. Suppose a recommendation system that is able to suggest the best parking spaces in a parking lot. A Spatial Skyline query may be evaluated to identify the best parking spaces. In this example, the data are changing, e.g., the driver's vehicle may move continuously or the availability of parking spaces may change frequently. Therefore, the Spatial Skyline set changes depending on the vehicle location and/or the availability of spaces. Particularly, the availability of a parking space is a changing non-spatial datum and the location of the vehicle is a moving query point.
SSQ on changing data may have several applications. They may be used in logistics of services and parking lots of festivals and events such as Rock in Rio, Pinkpop Festival, Lollapalooza, Glastonbury Festival, Olympic Games, FIFA World Cup and Super Bowl to which attend thousands of citizens and tourists from different regions and countries (Lande & Lande, 2008). In these events the parking time could be critical if customers have to find a parking space by themselves without any help or suggestion.
In addition, SSQ on changing data may be applied in case of emergency or natural disaster to identify the highly vulnerable regions near the most endangered areas in order to plan and organize a rescue; the affected regions change their status among attended and urgent attention and have an impact level, so the most urgent and vulnerable regions are attended first. The SSQ on changing data may also be used in reservation systems able to recommend on the basis of criteria that meet the user’s preferences. For example, a user may be interested in booking an event preferring a lower price seat which is close to the stage, to the exit and to the initial seat of any row; the seats availability may change because other customers canceled a reservation or made a new one. Another use could be in a mobile application to reserve a table for n people in a restaurant which is open, well rated and is on the way home, this means close to the user in motion and close to home. Lastly, the problem of answering SSQ on changing data is hard to solve because data is constantly changing while the Spatial Skyline set is been computed in polynomial time.
Key Terms in this Chapter
Skyline: Set of non-dominated objects.
Delaunay Graph: Delaunay Triangulation which is the dual problem of a Voronoi diagram.
Dominance: An object a dominates another object b if and only if a is better than or equal to b on all dimensions of a multidimensional function and a is better than b on at least one dimension.
Progressive Skyline Algorithm: Algorithm that produces results over its execution, i.e., it returns initial results before identifying the whole skyline.
Non-Spatial Dimension: Characteristic of an object that is not related to spatial data. It is commonly static.
Convex Hull: It is the convex polygon formed by a given set of points in the Euclidean plane, whose vertices are some of these points; the remaining points are inside the polygon.
Spatial Dimension: Corresponds to a spatial preference for a query point, i.e., the minimization of the distance from an object to a query point.
Voronoi Diagram: It is a geometric construction that divides the space into different regions of the Euclidean plane. It was studied by mathematician, Georgy Voronoi. Each point p has a corresponding region called Voronoi cell which consists of all points closer than any other point.
Skyline Techniques: Set of strategies for identifying incomparable elements that are characterized by multi-dimensional properties.