1(College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang 314001) 2(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027)
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.