Top-k Query Processing of Reverse Skyline in Metric Space

Unlike the traditional metric skyline query, this paper studies a novel skyline query in metric space, called metric top-k reverse skyline (MkRS), which executes the skyline computation from a reverse perspective. Given a query object q and a monotonic preference function f, MkRS returns k subsets which contain exactly m objects of the input dataset P such that each subset G has q in its metric skyline. When evaluating the query, we need to perform exhaustive search of selecting m objects from n objects of dataset P and metric skylines for each combination. These computations are costly due to the extremely large search space. We first present STS (sort and threshold skyline) algorithm to speed-up the computation, which exploits the sorting machinery so that only a part of subsets needs examining and STS can early stop the computation. Then, we reuse the information produced during index accessing which reduces more than 80% I/O accesses of STS and propose the customized algorithm rSTS based on STS. The experimental results show that our proposed algorithms are effective and efficient.