云计算环境下的容错并行Skyline查询算法研究

云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时,其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能,不能保证故障情况下查询继续正确执行。为此,提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline,FTPS)。该算法通过故障监测和任务迁移,使得能够在查询过程中及时发现故障,并将故障节点的计算任务迁移到副本节点,保证查询的正确执行。理论分析和实验证明,FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。     

RDF数据的Skyline优化查询

为解决海量RDF数据的Skyline查询问题,通过分析现有Skyline查询算法的优缺点,提出一种针对海量RDF数据的查询机制。对RDF数据的存储结构进行分析,根据RDF数据垂直存储结构,设计一种候选Skyline点筛选策略,提前修剪部分非Skyline元组,减少Skyline支配点计算的数据量;在筛选的基础上,给出基于MapReduce的Skyline并行化查询算法。实验结果表明,提前筛选能有效减小查询的数据集,并行化算法能够有效提高查询的效率。     

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

本文提出了一种新的分布环境中的Skyline查询算法--一种新的四阶段Skyline算法FDSL。现有的算法，如Distributed Skylining算法，在节点数m较大时会消耗大量的网络带宽。FDSL算法在任意数据集上只需要四次交互就能完成，并且通过剪除不必要的对象来减少网络带宽的消耗。本文通过模拟数据验证了FDSL算法的效率。实验表明，当节点点数m大于4时，FDSL算法的性能比现有算法提高了15％～30％。     

REPS:一种高效的容错并行概率流Skyline查询方法

概率数据流的并行Skyline查询作为当前大数据分析的一个重要方面,在诸多实际应用中发挥着重要作用。针对并行概率流Skyline查询过程中因发生故障而导致查询结果不准确和查询中断等问题,提出了一种基于复制的容错并行Skyline查询方法REPS。该方法选择参与并行处理的计算节点作为副本节点,并采用层次-循环式数据副本放置策略,选择优先级高的副本恢复数据来保证数据恢复的高效性;同时将故障检测、丢失数据恢复和查询过程恢复贯穿于整个查询更新过程中,以减少容错处理的额外通信和计算开销,并实现快速的容错并行查询。实验结果表明,REPS方法不仅在无故障发生和单个节点失效时具有较高的查询处理效率,而且对于多节点失效情形,仍然能够保持较高的查询处理速率且满足查询需求。     

基于MapReduce的Skyline查询处理算法

Skyline查询是一个典型的多目标优化查询,在多目标优化、数据挖掘等领域有着广泛的应用。现有的Skyline查询处理算法大都假定数据集存放在单一数据库服务器中,查询处理算法通常也被设计成针对单一服务器的串行算法。随着数据量的急剧增长,特别是在大数据背景下,传统的基于单机的串行Skyline算法已经远远不能满足用户的需求。基于流行的分布式并行编程框架MapReduce,研究了适用于大数据集的并行Skyline查询算法。针对影响MapReduce计算的因素,对现有基于角度的划分策略进行了改进,提出了Balanced Angular划分策略;同时,为了减少Reduce过程的计算量,提出了在Map端预先进行数据过滤的策略。实验结果显示所提出的Skyline查询算法能显著提升系统性能。     

高效的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查询问题。实验结果表明,该算法可以在牺牲少量精度的情况下提高查询效率。     

不确定数据流上的并行反Skyline查询

作为Skyline查询的一种重要变体,不确定数据流上的反Skyline查询已经成为研究的热点。已有的单机算法无法应对诸如高速数据流、高数据维度、大滑动窗口等情况,相应提出并行查询处理算法PRSUDS。算法采用基于角度划分的分发策略将处理任务分发至各并行节点,给出该分发策略的正确性证明,进而设计、实现算法的并行处理框架。实验结果表明PRSUDS算法较单机算法具有更好的综合性能,更能满足数据流查询的实时性要求。     

一种高效的分布式动态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算法的有效性。     

垂直分布数据集上的安全Skyline查询算法

Skyline查询是指从多维数据集中筛选出不被其他任何数据点支配的数据点,是一种重要的数据分析方法。近年来,随着隐私保护需求的不断增长,分布式数据集上保护隐私的Skyline查询算法也受到越来越多关注。然而,现有的垂直分布数据集上的Skyline查询方案数据以明文存储,不能实现数据的隐私保护。为此,深入研究了垂直分布式数据集上保护隐私的Skyline查询问题,提出了一种抗合谋攻击的多方垂直分布数据集上的Skyline查询协议。理论分析证明了提出协议的正确性和安全性。此外,通过理论分析和模拟实验对协议运行效率进行了评估,结果显示新方案具有较高的运行效率。     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。     

Skyline查询处理

对目前的Skyline查询方法进行分类和综述.首先介绍Skyline查询处理问题产生的背景,然后介绍Skyline查询处理的内存算法,并从带索引和不带索引两个方面对现有的外存Skyline查询处理方法进行分类介绍,在每组算法后,都对该组算法进行了性能评价,然后介绍不同子空间上的多SKyline查询处理模型——SKYCUBE的概念和相关研究.另外,还介绍了不同应用环境下解决Skyline查询处理的策略以及Skyline查询处理问题的扩展,最后归结出Skyline查询处理后续研究的几个方向.     

k-dominant Skyline query algorithm for dynamic datasets

At present,most k-dominant Skyline query algorithms are oriented to static datasets,this paper proposes a k-dominant Skyline query algorithm for dynamic datasets.The algorithm is recursive circularly.First,we compute the dominant ability of each object and sort objects in descending order by dominant ability.Then,we maintain an inverted index of the dominant index by k-dominant Skyline point calculation algorithm.When the data changes,it is judged whether the update point will afect the k dominant Skyline point set.So the k-dominant Skyline point of the new data set is obtained by inserting and deleting algorithm.The proposed algorithm resolves maintenance isue of a frequently updated database by dynamically updating the data sets.The experimental results show that the query algorithm can efectively improve query eficiency.     

Skyline代表点的选择*

Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.     

无线传感器网络中基于聚簇结构的Skyline查询方法

现有的基于单服务器的Skyline查询算法已经不能很好地应用于无线传感器网络这类分布式多跳自组织网络中。基于聚簇结构的Skyline查询算法就是针对 这类特定的网络结构而提出的。该算法采用基于聚簇的路由结构,为了减少Skyline查询处理过程中传感器节点的通信开销,挑选具有最大支配力的数据元组作为全局过滤元组来过滤不满足Skyline条件的数据。同时,在Skyline查询处理过程中引入滑动窗口机制,该机制也能有效地降低通信开销。大量的仿真实验结果显示,所提Skyline查询算法在确保能耗的基础上仍然具有很好的性能。     

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.