MSSQ: Manhattan Spatial Skyline Queries

• We develop an efficient algorithm for spatial skyline queries in L1 metric.
• We also present an algorithm for queries moving vertically or horizontally.
• Our algorithms can easily be parallelized by computing each skyline independently.
• Our algorithms straightforwardly extend for L∞L∞ distance.
• Evaluations show that our algorithms are faster than the current approaches.

Skyline queries have gained attention lately for supporting effective retrieval over massive spatial data. While efficient algorithms have been studied for spatial skyline queries using the Euclidean distance, these algorithms are (1) still quite computationally intensive and (2) unaware of the road constraints. Our goal is to develop a more efficient algorithm for L1 distance, also known as Manhattan distance, which closely reflects road network distance for metro areas. We present a simple and efficient algorithm which, given a set P of data points and a set Q   of query points in the plane, returns the set of spatial skyline points in just O(|P|log|P|)O(|P|log|P|) time, assuming that |Q|≤|P||Q|≤|P|. This is significantly lower in complexity than the best known method. In addition to efficiency and applicability, our algorithm has another desirable property of independent computation and extensibility to L∞L∞ norm distance, which naturally invites parallelism and widens applicability. Our extensive empirical results suggest that our algorithm outperforms the state-of-the-art approaches by orders of magnitude. We also present efficient algorithms that report the changes of the skyline points when single or multiple query points move along the x- or y-axis.