中文摘要：

不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS（metric top-k reverse skyline）.MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS（sort and threshold skyline）,它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS（reuse STS）,进一步减少了STS中80％以上的I/O访问.大量的实验表明提出的算法有效、快速.

英文摘要：

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 rn 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.