度量空间中的Top-k反向Skyline查询算法  

Top-k Query Processing of Reverse Skyline in Metric Space

作　　者：张彬[1] 蒋涛[1] 高云君[2] 乐光学[1] 

机构地区：[1]嘉兴学院数理与信息工程学院,浙江嘉兴314001 [2]浙江大学计算机科学与技术学院,杭州310027

出　　处：《计算机研究与发展》2014年第3期627-636,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61379033;61003049);浙江省自然科学基金项目(LY12F02047;LY12F02019);中央高校基本科研业务费专项资金项目(2013QNA5020;2012QNA5018);浙江大学紫金计划重点项目;嘉兴学院南湖学院科研重点资助项目

摘　　要：不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-kreverse 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.

关 键 词：查询 算法 度量空间 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP392[自动化与计算机技术—计算机科学与技术]