主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
蒋涛,张彬,余法红,柳晴,周傲英.排序的相互k-Skyband查询算法.软件学报,2015,26(9):2297-2310
排序的相互k-Skyband查询算法
Randed Processing for Mutual k-Skyband Query
投稿时间:2014-03-19  修订日期:2014-07-31
DOI:10.13328/j.cnki.jos.004704
中文关键词:  算法  排序  k-Skyband  相互k-skyband  空间数据库
英文关键词:algorithm  ranking  k-Skyband  mutual k-Skyband  spatial database
基金项目:浙江省自然科学基金(LY14F020038); 国家自然科学基金(61379033, 61003049); 嘉兴学院南湖学院科研重点资助项目
作者单位E-mail
蒋涛 嘉兴学院 数理与信息工程学院, 浙江 嘉兴 314001  
张彬 嘉兴学院 数理与信息工程学院, 浙江 嘉兴 314001 jxbinzhang@gmail.com 
余法红 嘉兴学院 数理与信息工程学院, 浙江 嘉兴 314001  
柳晴 浙江大学 计算机科学与技术学院, 浙江 杭州 310027  
周傲英 华东师范大学 软件学院, 上海 200062  
摘要点击次数: 3216
全文下载次数: 2441
中文摘要:
      不同于传统的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.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利