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

不同于传统的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.