基于MapReduce的Skyline查询处理算法

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

基于MapReduce的连续概率Skyline查询

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

云环境下基于超球面投影分区的Skyline计算

目前,Skyline查询在集中式数据库、分布式数据库、数据流及分类属性数据集上的良好应用前景,使其成为当前数据库界研究的重点和热点之一,受到了学术界和工业界的广泛关注,它作为一种重要的数据挖掘技术广泛应用于多目标优化、城市导航系统、用户偏好查询及约束决策、智能防御系统以及地理信息系统等领域.随着人类可以采集和利用的数据信息的急剧增长,如何处理大数据的Skyline查询成为急需解决的问题.针对云计算环境,在Map-Reduce框架下设计并实现了基于超球面投影分区的分布式Skyline算法HSPD-Skyline,其主要思想是通过对高维数据点的超平面投影映射,即由空间坐标转换为超球面坐标,可以有效提高分区内数据点的平均减枝力度,降低Skyline的计算代价.同时,使用基于空间分区树的启发式策略HA-SPT,进一步提高了HSPD-Skyline算法的处理效率.通过详细的理论分析和实验验证表明,在不考虑数据分布和进一步优化算法的条件下,提出的HSPD-Skyline算法的总体性能(可扩展性、Skyline查询时间等)优于同类算法.     

MapReduce框架下基于B 树的高维索引

针对MapReduce数据块处理机制、高维数据分布特征和KNN查询需求,本文设计一种基于B 树的高维索引结构（iPartition）,创新性提出基于主成分区分度的优化数据划分策略和邻接数据域分散存储等原则,将数据均匀划分到不同的Slave节点,使尽可能多的数据域对计算共同贡献,提升MapReduce任务处理并行性;利用B 树构造分布式的双层索引实现查询时数据范围快速过滤,降低高维计算代价。实验表明,iPartition在高维数据近似查询环境下,具有良好的性能和扩展性。     

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

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

一种网格化高并发Skyline查询处理方法

为减少冗余支配测试对Skyline查询性能的影响并提高Skyline查询处理的效率，本文将测试单位扩大为网格，并设计了一种基于网格分层划分的Skyline查询方法.通过不断缩小Skyline点集所在网格的方式，使网格之间的支配关系与点支配关系重合，从而避免了点与点之间大量无效的支配测试，提升了Skyline查询处理的效率.方法中同一层的网格可并行计算，且层次计算过程可达到任意精度，适用于计算能力有限但对结果精度要求不高的场合.实验结果表明，方法与现有Skyline查询处理方式相比具有数据吞吐量大、响应速度快等特点，在拥有高性能GPU或多核CPU等高并发环境下其优势更为明显.     

基于网格和密度的海量数据增量式离群点挖掘算法

处理海量和高维数据已经成为设计离群点算法面临的重要任务和挑战,针对海量数据的特点提出一种基于网格和密度的增量式离群点挖掘算法IGDLOF,算法的基本思想为:采用网格的七元组信息减少数据维数和数量,利用增量更新减少内存需求.通过代表点过滤相应的主体数据,先判断再进行近似密度计算的方法减少计算量,降低算法的复杂度.通过在真实和仿真数据集的测试表明,IGDLOF增量算法可与LOF算法保持相同的精确度,而执行效率得到显著的提高.     

基于混合网格划分的子空间高维数据聚类算法

提出一种基于混合网格划分的子空间高维数据聚类算法.该算法消除了各个属性分量数值范围大小对计算的影响;有效去除冗余属性以提高聚类准确性与降低时间复杂度.根据数据分布情况灵活选择固定网格划分或是自适应网格划分,利用这二种不同的网格划分方法具有的优点,以实现进一步降低算法的时间复杂度和提高聚类结果的准确性,并使算法具有更优的可伸缩性.实验使用仿真数据表明,该算法在处理具有属性值域范围大的高维大规模数据时是实用有效的.     

基于矩阵分解的协同过滤算法的并行化研究

基于矩阵分解的协同过滤算法是近几年提出的一种协同过滤推荐技术,但其每项预测评分的计算都要综合大量评分数据,同时在计算时还需要存储庞大的特征矩阵,用单一节点来进行推荐将会遇到计算时间和计算资源的瓶颈。通过对现有的基于ALS(最小二乘法)的协同过滤算法在Hadoop上并行化实现的原理和特点进行深入的研究,得到了传统的迭代式算法在Hadoop上运算效率不高的原因。根据迭代式MapReduce思想,提出了循环感知任务调度算法、缓存静态数据、任务循环控制、迭代终止条件检测等方法。通过在Netflix数据集上的实验表明,迭代式MapReduce思想提高了基于ALS的协同过滤算法的并行化计算的效率。     

RDF数据的Skyline优化查询

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

基于高维数据流的异常检测算法

传统基于欧氏距离的异常检测算法在高维数据检测中存在精度无法保证以及运行时间过长的问题。为此,结合高维数据流的特点运用角度方差的方法,提出一种改进的基于角度方差的数据流异常检测算法。通过构建最佳数据集网格和最近数据网格的小规模数据流计算集,以快速即时地衡量最新数据点的异常程度,将改进的算法用于无线传感器网络采集的电梯真实数据流检测,实现电梯故障检测。实验结果表明,与ABOD、HODA等算法相比,改进算法能有效识别高维数据流中的异常点,可适用于实时性要求高的传感器高维数据流。     

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.     

MapReduce与Spark用于大数据分析之比较

随着大数据时代的到来,海量数据的分析与处理已成为一个关键的计算问题.本文评述了MapReduce与Spark两种大数据计算算法和架构,从背景、原理以及应用场景进行分析和比较,并对两种算法各自优点以及相应的限制做出了总结.当处理非迭代问题时,MapReduce凭借其自身的任务调度策略和shuffle机制,在中间数据传输数量以及文件数目方面性能要优于Spark;而在处理迭代问题和一些低延迟问题时,Spark可以根据数据之间的依赖关系对任务进行更合理的划分,相较于MapReduce有效地减少中间数据传输数量与同步次数,提高系统的运行效率.     

一种在源数据稀疏情况下的流形学习算法研究

传统的流形学习算法能有效地学习出高维采样数据的低维嵌入坐标,但也存在一些不足,如不能处理稀疏的样本数据.针对这些缺点,提出了一种基于局部映射的直接求解线性嵌入算法(Solving Directly Linear Embedding,简称SDLE).通过假定低维流形的整体嵌入函数,将流形映射赋予局部光滑的约束,应用核方法将高维空间的坐标投影到特征空间,最后构造出在低维空间的全局坐标.SDLE算法解决了在源数据稀疏情况下的非线性维数约简问题,这是传统的流形学习算法没有解决的问题.通过实验说明了SDLE算法研究的有效性.     

二次式距离上基于SVD的高维图像索引方法

向量近似方法（vector approximation file）是解决高维索引中维数灾难问题的一种有效方法，但是它不能直接支持二次式距离上的近邻搜索，为此，提出一种基于奇异值分解（SVD）的二次式距离上的向量近似方法，通过奇异值分解技术将二次式距离变换为欧氏距离形式，对变换后的特征向量进行近似得到近似向量。进行近邻搜索时采用低维过滤算法，先在较高能量的低维子空间内计算近似距离进行过滤，再对过滤结果进行高维距离计算。实验结果表明，低维过滤算法可以过滤掉大部分特征向量，而只有小部分数据需要进行高维距离运算，该方法可以显著提高大型高维图像数据库的近邻搜索性能。     

基于MapReduce的矩阵分解推荐算法研究

矩阵分解是近几年提出的一种协同过滤推荐技术,但其每项预测评分的计算都要综合大量评分数据,同时在计算时还需要存储庞大的特征矩阵,用单一结点来进行推荐将会遇到计算时间和计算资源瓶颈。结合MapReduce分布式计算框架和矩阵分解推荐算法,设计了一种基于MapReduce的矩阵分解推荐算法来解决该问题,利用Hadoop的分布式缓存技术和MapFile文件结构解决了大特征矩阵在多结点间的高效共享问题并实现了多正则因子的并行处理。通过在Netflix数据集上的实验表明,该MapReduce算法及数据存储方案能带来较高的加速比,从而提高了推荐算法的计算效率。     

MapReduce框架下的Skyline云资源选择算法

文中研究了MapReduce框架下的云资源选择算法 。该算法利用概率筛选的方法计算资源节点属于Skyline结果集的概率,并通过阈值过滤来降低MapReduce中的心跳频率,以达到优化网络流量的目的。     

海量高维向量的并行Top-k连接查询

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.     

一种基于极大熵的快速无监督线性降维方法

现实世界中高维数据无处不在,然而在高维数据中往往存在大量的冗余和噪声信息,这导致很多传统聚类算法在对高维数据聚类时不能获得很好的性能.实践中发现高维数据的类簇结构往往嵌入在较低维的子空间中.因而,降维成为挖掘高维数据类簇结构的关键技术.在众多降维方法中,基于图的降维方法是研究的热点.然而,大部分基于图的降维算法存在以下两个问题:(1)需要计算或者学习邻接图,计算复杂度高;(2)降维的过程中没有考虑降维后的用途.针对这两个问题,提出一种基于极大熵的快速无监督降维算法MEDR. MEDR算法融合线性投影和极大熵聚类模型,通过一种有效的迭代优化算法寻找高维数据嵌入在低维子空间的潜在最优类簇结构. MEDR算法不需事先输入邻接图,具有样本个数的线性时间复杂度.在真实数据集上的实验结果表明,与传统的降维方法相比, MEDR算法能够找到更好地将高维数据投影到低维子空间的投影矩阵,使投影后的数据有利于聚类.