基于MapReduce的连续概率Skyline查询

大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。     

RDF数据的Skyline优化查询

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

MapReduce框架下基于超平面投影划分的Skyline计算

近年来,Skyline计算在决策应用中起着越来越重要的作用.针对单机处理的研究已较为成熟.现今大数据爆炸,Skyline计算面临着大数据处理的问题.MapReduce是一个并行模型,广泛应用于数据密集型应用处理中.众所周知,MapReduce处理要求任务是可分解的.Skyline计算在MapReduce上执行时,分解任务的方法有网格划分、基于角度的划分等.网格划分仅在数据维度较低时表现良好;基于角度的划分适用于低维和高维数据,但在划分前需要一个复杂并且费时的坐标转换过程.现采用一种与基于角度的划分类似的基于超平面投影的划分来分解数据集,这种划分适用于低维和高维数据,而且其在划分前的坐标转换较为简单.根据超平面投影的划分提出了一种在MapReduce上处理Skyline计算的算法MR-HPP(MapReduce with hyperplane-projections-based partition),并在该算法的过滤阶段提出了一种有效的过滤算法PSF(presorting filter).大量基于Hadoop平台的对比实验表明该算法的准确性、高效性和稳定性.     

基于MapReduce的预处理高效Skyline算法

现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

无线传感器网络数据环区域查询处理算法

针对无线传感器网络节点能量高效问题以及Skyline查询位置属性决策问题,提出了基于无线传感器网络数据环区域查询处理算法。该算法以查询位置P为中心进行数据环划分,查询位置P最近的K个Skyline值时,根据剪枝策略只需对距离小于P的其它属性值进行比较,从而缩小了数据规模,提高了查询效率。另外,环内节点采用链簇式结构组织,环内查询处理过程采用串行数据处理与并行数据处理模式,从而提高了K-Skyline的数据查询能耗与节点处理延迟。仿真实验表明,数据环区域查询处理算法比Flooding算法与TAG算法具有更小的数据处理能耗和延迟。     

MapReduce框架下的Skyline结果优化算法

随着大数据时代的到来,数据量和数据复杂度急剧提高,Skyline查询结果集规模巨大,无法为用户提供精确的信息.MapReduce作为并行计算框架,已广泛应用于大数据处理中.本文提出了MapReduce框架下基于支配个数的结果优化算法(MR-DMN),解决了大数据环境下的Skyline结果集优化问题.大量的实验表明:算法具有良好的时间和空间效率.     

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),并针对这三种算法进行了系统的实验比较,得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。     

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

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

时空轨迹大数据分布式蜂群模式挖掘算法

针对时空轨迹大数据的蜂群模式挖掘需求,提出了一种高效的基于MapReduce的分布式蜂群模式挖掘算法。首先,提出了基于最大移动目标集的对象集闭合蜂群模式概念,并利用最小时间支集优化了串行挖掘算法;其次,提出了蜂群模式的并行化挖掘模型,利用蜂群模式时间域无关性,并行化了聚类与子时间域上的蜂群模式挖掘过程;第三,设计了一个基于MapReduce链式架构的分布式并行挖掘算法,通过四个阶段快速地实现了蜂群模式的并行挖掘;最后,在Hadoop平台上,使用真实交通轨迹大数据集对分布式算法的有效性和高效性进行了验证与分析。     

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

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

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

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

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

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

基于动态双子种群的差分进化K中心点聚类算法

随着海量大数据的出现,聚类算法需要新型计算模式来提高计算速度与运行效率。本文提出一种基于动态双子种群的差分进化K中心点聚类算法DGP-DE-K-mediods(Dynamic Gemini Population based DE-K-mediods)。DGP-DE-K-mediods利用动态双子种群方法,解决聚类算法在维持种群密度的时候避免陷入局部最优的问题;采用差分进化(Differential Evolution, DE)算法来提高全局最优能力的强健性;基于Hadoop云平台来并行处理DGP-DE-K-mediods,加快算法的运行速度和效率;描述基于MapReduce的并行聚类算法的编程过程;DGP-DE-K-mediods利用UIC的大数据分类的案例数据和网络入侵检测这种大数据应用来仿真算法的效果。实验结果表明,与已有的聚类算法相比,DGP-DE-K-mediods在检测精度、运行时间上有明显的优势。     

MapReduce技术在物资调运与配载问题中的应用

针对用于求解复杂物资调运及配载问题的多目标遗传算法耗时较长的问题,设计了基于云计算MapReduce技术的并行化部署和改进方案。实验对比了算法在多种串行、并行环境下的时效性,证实了MapReduce架构在一定环境下能较大幅度提高算法的时耗性能。     

Efficient k-dominant skyline query over incomplete data using MapReduce

Skyline queries are extensively incorporated in various real-life applications by filtering uninteresting data objects. Sometimes, a skyline query may return so many results because it cannot control the retrieval conditions especially for highdimensional datasets. As an extension of skyline query, the kdominant skyline query reduces the control of the dimension by controlling the value of the parameter kto achieve the purpose of reducing the retrieval objects. In addition, with the continuous promotion of Bigdata applications, the data we acquired may not have the entire content that people wanted for some practically reasons of delivery failure, no power of battery, accidental loss, so that the data might be incomplete with missing values in some attributes. Obviously, the k-dominant skyline query algorithms of incomplete data depend on the user definition in some degree and the results cannot be shared. Meanwhile, the existing algorithms are unsuitable for directly used to the incomplete big data. Based on the above situations, this paper mainly studies k-dominant skyline query problem over incomplete dataset and combines this problem with the distributed structure like MapReduce environment. First, we propose an index structure over incomplete data, named incomplete data index based on dominate hierarchical tree (ID-DHT). Applying the bucket strategy, the incomplete data is divided into different buckets according to the dimensions of missing attributes. Second, we also put forward query algorithm for incomplete data in MapReduce environment, named MapReduce incomplete data based on dominant hierarchical tree algorithm (MR-ID-DHTA). The data in the bucket is allocated to the subspace according to the dominant condition by Map function. Reduce function controls the data according to the key value and returns the k-dominant skyline query result. The effective experiments demonstrate the validity and usability of our index structure and the algorithm.