Top-k Manhattan spatial skyline queries

In this paper, we consider the top-k Manhattan spatial skyline query problem with respect to monotone scoring functions which quantifies, for each point in P, how well it fits the given query under the L1 distance. We present an algorithm that computes the top-k skyline points in time near linear in the size of P, assuming that f and k are part of the input. The presented strategy improves over the direct approach of using the state-of-the-art algorithm to compute the Manhattan spatial skyline and then filtering it by the scoring function by a log⁡(|P|) factor. Our empirical results suggest that our algorithm outperforms the direct approach by an order of magnitude.