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

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

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

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

分布式环境下的Skyline代表点查询

为了克服Skyline查询的不足即结果集大小无法控制,提出了Skyline代表点查询,返回k个可描述全局Skyline轮廓的Skyline代表点。研究了分布式环境下的Skyline代表点查询,提出了Naive算法和FDRA。Naive算法首先转移每个子节点上满足条件的两个局部代表点,再通过比较传来的局部代表点间的评价函数值大小决定子节点是否需要传送余下的局部点,以实现剪枝非代表点;与之相比,FDRA的改进在于过滤元组的选择,运用反馈方法,将每次动态更新最大评价函数值的点作为过滤元组,大大降低了计算代价,中心服务器每次只发送过滤元组到分布节点,这样可以尽早且最大限度地剪枝不可能成为代表的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产品组合发现问题,这也是一个NP-hard问题。该问题着力于返回所有拥有最大折扣率的Skyline产品组合。考虑到面向最有效的Skyline产品组合发现问题的实际算法并不适用于过大或者高维度的数据库,我们设计了一种增量贪婪算法。实验结果证明了该算法的有效性和高效性。     

移动环境下的连续概率Skyline查询

主要研究查询点固定,目标对象移动且移动对象在位置不确定的情况下,成为Skyline对象的可能性（采用概率形式表示）,并实现移动对象位置不确定条件下的连续Skyline查询。定义了影响P-Skyline集合的Events,提出了一个基于事件的算法E-CPS,该算法并通过计算,跟踪和处理Events来更新P-Skyline集合。该方法大大减少了算法的查找和计算开销,提高了运算效率。     

道路网环境下K-支配空间Skyline查询方法

已有的天际线（Skyline）查询主要聚焦于单用户场景,并基于单用户模型进行Skyline计算,而较少考虑道路网环境下多用户情况. 为了弥补已有方法无法解决道路网络环境下多用户偏好和权重Top-k Skyline查询问题的不足,提出了一种基于道路网环境下多用户偏好Top-k Skyline（multi-user preference Top-k Skyline,MUP-TKS）查询方法. 在道路网环境下考虑多用户的不同偏好和权重进行Skyline查询,可以快速得到符合查询用户群偏好和权重的结果集,提供用户群更好的决策支持.MUP-TKS首先通过所提的G_DBC算法,利用道路网中数据点与查询点之间的位置关系和新的索引结构Vor-R^*-DHash剪枝、过滤数据点,从而得到距离较优集;再利用静态Skyline集不变的性质,预先计算、保存该集合;然后通过所提的新支配关系对距离较优集与静态Skyline集取并集后的集合S进行放松支配;最后利用所提TK_DC算法对经过放松支配后的候选结果集打分,依据数据点得分情况,排序输出Top-k个结果集返回用户群. 理论研究与实验表明,所提方法具有较好的效率与可靠性.

     

多因素时间序列Skyline的快速查询算法

在给出多因素时间序列Skyline(MFTS)形式化定义的基础上,提出一种MFTS快速查询算法,获得并存储各时间点上的多因素值,计算每个最小时间区间的准MFTS,从而得到指定区间的MFTS。实验分析结果表明,在时间序列重合较少的情况下,该算法具有较好的查询效率。     

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

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

云计算环境下并行分布式数据挖掘平台研究

网络技术在带给人们大量信息的同时,也极大地增加了人们从海量数据中发现有用知识的难度,而解决这一问题的努力促进了数据挖掘技术的出现和快速发展。云计算是能够提供动态资源池、虚拟化和高可用性的计算平台,云计算开发平台可被用来开发高性能应用程序。研究云计算环境下并行分布式数据挖掘平台的3个层次,依下而上为分布式计算层,知识发现平台层以及用户应用层。     

基于数据垂直划分的高效并行Skyline查询

基于数据垂直划分的分布并行Skyline查询算法大多并行性较低,无法适应海量分布式数据的快速响应要求。为此,在BDS算法的基础上提出一种更高效的分布并行Skyline查询算法PDS-VP。其中,节点被分为协调者与参与者,原本由协调者节点完成的随机访问和本地Skyline计算分发给各参与者节点进行处理,以提高算法的执行效率。实验结果证明,该算法提高了原算法的并行性和运行效率。     

云计算环境下的分布存储关键技术

云计算作为下一代计算模式,在科学计算和商业计算领域均发挥着重要作用,受到当前学术界和企业界的广泛关注.云计算环境下的分布存储主要研究数据在数据中心上的组织和管理,作为云计算环境的核心基础设施,数据中心通常由百万级以上节点组成,存储其上的数据规模往往达到PB级甚至EB级,导致数据失效成为一种常态行为,极大地限制了云计算的应用和推广,增加了云计算的成本.因此,提高可扩展性和容错性、降低成本,成为云计算环境下分布存储研究的若干关键技术.针对如何提高存储的可扩展性、容错性以及降低存储的能耗等目标,从数据中心网络的设计、数据的存储组织方式等方面对当前分布存储的关键技术进行了综述.首先,介绍并对比了当前典型的数据中心网络结构的优缺点;其次,介绍并对比了当前常用的两种分布存储容错技术,即基于复制的容错技术和基于纠删码的容错技术;第三,介绍了当前典型的分布存储节能技术,并分析了各项技术的优缺点;最后指出了当前技术面临的主要挑战和下一步研究的方向.     

MapReduce框架下的Skyline计算

由于Skyline查询广泛应用于多目标决策、数据可视化等领域,近年来成为数据库领域的一个研究热点。针对云计算环境,在MapReduce框架下设计并实现了Skyline算法。MapReduce是一个运行在大型集群上处理海量数据的并行计算框架,其主要思想是任务的分解与结果的汇总。基于不同的数据划分思想,实施了三种Skyline并行算法,分别是基于MapReduce的块嵌套循环算法(MapReduce based block-nested-loops,MR-BNL)、基于MapReduce的排序过滤算法(MapReduce based sort-filter-skyline,MR-SFS)以及基于MapReduce的位图算法(MapReduce based bitmap,MR-Bitmap),并针对这三种算法进行了系统的实验比较,得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。     

云计算研究

云计算模式是在基础设施即服务（IaaS）、平台即服务（PaaS）、软件即服务（SaaS）、分布式计算、并行计算和网格计算等概念演进并产生的结果。云计算模式是一种全新的计算应用模式,将会成为人们获取服务的主导方式。本文首先介绍云计算在业界中的概念,接着分析云计算和相关计算,最后关于云计算发展的前景进行展望。     

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

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

一种基于云超级节点的移动P2P存储模型及其传输机制研究

移动P2P具有一些良好的特点,但是由于移动设备之间的多维异构,设备具有较低的带宽,较高的数据传输代价,加之资源分布的任意性,使得基于MP2P的数据存储和传输受到了极大的限制.如何采用针对性的存储方式及其相应的传榆方式是一个重要的研究方向.本文考虑到存储节点的空间限制,数据传输的可靠性等综合因素,提出一种基于云超级节点的移动P2P的存储和传输模型,将部分数据传输到合适的云节点上进行存储,利用云端节点的高可靠性提供较高质量的MP2P服务.结果显示,本文的算法性能较之以往类似的算法有较大的性能提高,同时在存储空间上节约了50％以上,实验和理论分析充分证明了本文提出的存储和传输策略及相应算法是正确、有效的.     

云计算与网格计算的比较

介绍了当前计算方法的发展趋势,对当前主流的云计算和网格计算两种计算方法从定义、特点方面进行了详细的阐述,并对两种技术进行深入的分析比较,最终对其异同之处进行了概括总结。     

基于聚类和Skyline计算的云计算服务选择

针对云计算环境中存在着大量功能相同或类似而服务质量不同的服务,而实现对这些服务选取的方法往往具有效率低和实时性差的缺点,为此,提出了一种基于聚类和Skyline计算的云计算服务选择方法;首先,对各抽象服务类采用相似度矩阵进行分类,选取其中与用户服务请求最匹配的分类作为候选分类;然后,通过Skyline计算剔除各候选分类中的冗余服务,保留支配服务作为候选服务;最后,通过最大化效用函数来选取候选服务构成组合服务;仿真实验表明文中方法能高效地实现云计算环境下的服务选取,且与其它方法比较,与用户服务请求需求具有较高的匹配度,服务选择精确度达到100%,同时算法的时间复杂度较低,具有较大的优越性。