Increasingly, various contexts call for queries where one is seeking a set of objects (points) from the database that form a skyline (no other point dominates them). These queries have been dubbed skyline queries. They are specified through a set of points (qi) that are then used as a basis to define the criterion of dominance and select the points of interest (pj). For example, given a set of agent locations (qi), find a set of potential restaurants (pj) where they could meet; given a set of explosion locations (qi), find the buildings (pj) that must be evacuated first; or, given a set of compromised nodes in a network, identify the nodes that must be isolated first. In many of these applications, the dominance relationship is exclusively spatial. Branch-and-bound algorithms have been introduced to address the general skyline query problem, without being restricted to spatial criteria.

Sharifzadeh et al. focus on skyline queries where the points pj and qi have coordinates in space and where the dominance relationship is based on proximity to the query points qi. They establish geometric relationships that enable them to reduce the search space and derive two different algorithms that are more efficient than the general-purpose skyline query algorithms. They further address the case where the query points qi are mobile (for example, agents are moving); they develop a dynamic algorithm that minimizes the amount of computation required to update the skyline as the query points move. Finally, they address applications where the query criterion is not based on Euclidean distance (for example, weights on network edges), and thus does not benefit from the same geometric properties as the spatial queries. For these, they introduce two alternative approaches.

In our increasingly mobile computing infrastructure, the problem addressed in this paper is of highly practical utility. Finding efficient and accurate algorithms to solve it is critical. I found the paper easy to read. The theoretical foundation is fairly straightforward, and it is exploited in very innovative and interesting ways throughout the paper.