数据流上连续动态skyline查询研究

skyline查询能够从大规模数据集上计算满足多个标准的最优点.数据流上的skyline计算是数据流上最基本的查询操作之一,对于很多在线应用具有非常重要的意义,尤其在移动计算环境、网络监控、通信网络以及传感器网络等领域.不同于大部分传统的skyline研究,主要研究数据流上约束skyline和动态skyline计算问题.采用网格索引存储元组,提出了GBDS算法用于计算和维护动态skyline.通过为每个查询定义影响区域,使得在元组到达和失效时需要处理的元组个数最小化.理论分析和实验结果证明了提出方法的有效性.

一种基于动态Skyline和遗传粒子群优化的云服务组合方法

提出一种改进的基于动态Skyline和多种群遗传粒子群优化的云服务组合优化方法,旨在解决动态、不确定环境下大规模云服务组合优化问题.对云服务组合和服务质量(QoS)形式化描述,提出一种云服务组合优化模型;对Skyline操作进行建模的基础上,设计Skyline云服务动态更新算法,以满足云服务因临时加入、退出及QoS变化而引起的动态性和不确定性需求;最后,设计一种新的云服务组合优化算法,算法采用动态Skyline操作和用户约束降低问题求解空间,并基于种群相似性和遗传操作进行防早熟收敛处理.通过真实数据集和随机数据集的大量仿真实验,结果验证了本文算法的可行性和有效性.

基于MapReduce的增广动态Skyline查询处理方法

Skyline查询能够计算大规模的数据集中满足多个标准的最优解,被广泛应用于多目标决策等领域.动态skyline查询作为skyline查询的一种重要变体,其结果随着查询点的不同而动态改变,为用户在指定查询要求方面提供了更大的灵活性.然而,随着数据量的不断增加,动态skyline查询会产生大量的查询结果,忽略了查询点的维度方向性和数据的全局整体性,给用户的选择带来极大困难.因此,需要进一步优化动态skyline查询的结果集,提高全局整体性,过滤冗余数据.针对上述问题,提出一种基于MapReduce的增广动态skyline查询处理方法.该方法将原始数据按照维度信息进行分区,在多个节点并行计算动态skyline,优化传统动态skyline结果集,同时提供全局更优的结果供用户选择.在此基础上,针对用户给出某些维度的容忍度的情况,提出一种引入用户容忍度的增广动态skyline查询处理方法.该方法可以根据用户容忍度缩减增广动态skyline查询的原始数据集,很大程度上减少中间结果的比较次数,并且提高了结果集的准确度.大量实验证明,基于MapReduce的增广动态skyline查询处理方法具有更好的有效性、准确性和可用性.

一种高效的分布式动态Skyline查询算法

随着数据规模的增长,集中式环境下的查询算法已无法满足对大规模数据的查询需求,对此提出一种分布式动态Skyline查询(Distributed Dynamic Skyline Query,DDSQ)算法。DDSQ算法包含本地计算和合并计算两个过程。本地计算中,基于B树索引提出基础扫描算法(Basic Scan Algorithm based on B-tree,BSAB)来快速计算分布式动态Skyline候选集;提出优化的扫描算法(Optimized Scan Algorithm based on B-tree,OSAB),与BSAB相比,OSAB进一步减少了扫描空间,提高了计算效率。合并计算中,采用轮转策略对动态Skyline候选集进行合并计算。通过一系列实验验证了DDSQ算法的有效性。

高效的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算法不能有效解决面对各种折扣组合时的产品组合式查询。基于这个问题,我们首次定义并研究了最大优惠的Skyline产品组合发现问题,这也是一个NP-hard问题。该问题着力于返回所有拥有最大折扣率的Skyline产品组合。考虑到面向最有效的Skyline产品组合发现问题的实际算法并不适用于过大或者高维度的数据库,我们设计了一种增量贪婪算法。实验结果证明了该算法的有效性和高效性。

基于重用技术的相互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算法是有效的且保持了较高的效率.