高效的Top-k相互Skyline查询算法

Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I?O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I?O访问次数.

基于重用技术的相互Skyline查询算法

提出了一种新的Skyline查询,即相互Skyline查询(MSQ).给定一个对象集合P和一个查询对象q,MSQ返回一个对象集合,它的每个对象既在q的动态Skyline中,同时也在q的可逆Skyline中.基于传统的R-tree索引、重用堆信息技术以及启发式的修剪策略,显著降低了I/O成本,改进了基于BBS算法和BBRS算法实现的MSQ算法.几个真实数据集的实验表明提出的算法有效而高效,比一般MSQ算法快几个数量级.

一种最优的相互skyline查询算法

提出了一种最优的相互skyline搜索算法OMS,它的主要思想是R-tree搜索堆重用技术、窗口查询堆重用技术和高效的修剪策略.OMS与相互skyline算法RIBBS相比,它表现出更高的性能和效率.这是因为OMS消除了多次的动态skyline计算且挽救了更多的I/O成本.理论分析证明OMS计算相互skyline是最优的.在真实数据集上的大量实验结果表明,OMS算法是有效的且保持了较高的效率.