排序的相互k-Skyband查询算法  

Randed Processing for Mutual k-Skyband Query

作　　者：蒋涛[1] 张彬[1] 余法红[1] 柳晴[2] 周傲英[3] 

机构地区：[1]嘉兴学院数理与信息工程学院,浙江嘉兴314001 [2]浙江大学计算机科学与技术学院,浙江杭州310027 [3]华东师范大学软件学院,上海200062

出　　处：《软件学报》2015年第9期2297-2310,共14页Journal of Software

基　　金：浙江省自然科学基金(LY14F020038);国家自然科学基金(61379033;61003049);嘉兴学院南湖学院科研重点资助项目

摘　　要：不同于传统的k-Skyband查询方法,提出一种相互k-Skyband查询(Mk SB),它从对称角度执行Skyline查询,找出所有既在q的动态k-Skyband(Dk SB)中又在q的反向k-Skyband(Rk SB)中的数据对象.进一步地,为了更好地支持用户决策和数据分析,排序操作被引入到Mk SB算法中.因为Mk SB需要执行q的Dk SB和反向Rk SB,故它需要遍历索引多次,从而导致了大量冗余的I/O开销.利用信息重用技术和若干有效的修剪方法,Mk SB将多次的索引搜索合并成单次,极大地降低了I/O访问次数.同时,证明了基于窗口查询的Mk SB(WMk SB)算法具有最低的I/O代价.在真实与合成数据集上的实验结果表明,所提出的算法是有效的且明显胜过基于BBS的算法,尤其WMk SB算法具有极少的I/O开销,通常能够减少95%以上的冗余I/O.This paper proposes a novel Skyline query： mutual k-Skyband （MkSB） query. Unlike the traditional k-skyband query methods, MkSB executes the Skyline query from a symmetric perspective, and retrieves all the objects which are among both the dynamic k-Skyband （DkSB） of a specified query object q and the reverse k-Skyband （RkSB） of q. Furthermore, the ranking operation is introduced into MkSB due to its importance in data analysis and decision support. Since MkSB needs to perform DkSB and RkSB of q, it traverses the index multiple times, incurring much redundant I/O overhead. The proposed algorithms reduce multiple traversals to a single one, using the information reuse technology and several effective pruning heuristics that significantly cut down I/O accesses. Meanwhile, it is proved that MkSB based on window query （WMkSB） has the lowest I/O cost. Extensive experiments are conducted on both real and synthetic datasets, and the experimental results show that the proposed algorithms are efficient and outperform their competitors, i.e. the basic algorithm based on BBS （branch and bound Skyline）. Especially, WMkSB has the least I/O cost and often reduces more than 95% redundant I/O accesses.

关 键 词：算法 排序 k-Skyband 相互k-skyband 空间数据库 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]