Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950782 | Information Processing Letters | 2017 | 9 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wanbin Son, Fabian Stehn, Christian Knauer, Hee-Kap Ahn,