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

来源：软件学报杂志2015年第9期北京时间：

作者：蒋涛,张彬,余法红,柳晴,周傲英

单位：蒋涛，嘉兴学院 数理与信息工程学院, 浙江 嘉兴 31400111,张彬，嘉兴学院 数理与信息工程学院, 浙江 嘉兴 31400102,余法红，嘉兴学院 数理与信息工程学院, 浙江 嘉兴 31400103,柳晴，浙江大学 计算机科学与技术学院, 浙江 杭州 31002704,周傲英，华东师范大学 软件学院, 上海 20006205

摘要：不同于传统的k-Skyband 查询方法,提出一种相互k-Skyband 查询(MkSB),它从对称角度执行Skyline查询,找出所有既在q的动态k-Skyband(DkSB)中又在q的反向k-Skyband(RkSB)中的数据对象.进一步地,为了更好地支持用户决策和数据分析,排序操作被引入到MkSB算法中.因为MkSB 需要执行q的DkSB 和反向RkSB,故它需要遍历索引多次,从而导致了大量冗余的I/O 开销.利用信息重用技术和若干有效的修剪方法,MkSB 将多次的索引搜索合并成单次,极大地降低了I/O访问次数.同时,证明了基于窗口查询的MkSB(WMkSB)算法具有最低的I/O 代价.在真实与合成数据集上的实验结果表明,所提出的算法是有效的且明显胜过基于BBS 的算法,尤其WMkSB 算法具有极少的I/O 开销,通常能够减少95%以上的冗余I/O.

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

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