| 摘要: |
| 不同于传统的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 空间数据库 |
| DOI：10.13328/j.cnki.jos.004704 |
| 分类号: |
| 基金项目:浙江省自然科学基金(LY14F020038); 国家自然科学基金(61379033, 61003049); 嘉兴学院南湖学院科研重点资助项目 |
|
| Randed Processing for Mutual k-Skyband Query |
|
JIANG Tao1, ZHANG Bin1, YU Fa-Hong1, LIU Qing2, ZHOU Ao-Ying3
|
|
1.College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, China;2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;3.Software Engineering Institute, East China Normal University, Shanghai 200062, China
|
| Abstract: |
| 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. |
| Key words: algorithm ranking k-Skyband mutual k-Skyband spatial database |
