论文部分内容阅读
为应对大数据多样性挑战,一种方法是将多种类型的数据抽象成统一的通用数据类型,进而对不同类型的数据采用相同的算法进行处理。大数据泛构理念是以度量空间作为上述的通用数据类型。但由于度量空间中只有距离没有坐标,基于坐标的数据处理方法很难直接应用。一种常见的度量空间坐标化方法是选择一些数据作为参考点（支撑点）,以数据到各支撑点的距离作为其坐标,支撑点的好坏对索引性能有着关键性的影响。针对长期没有突破的度量空间支撑点选择问题,本文采用穷举法获取支撑点选择的性能上限,为揭示现有支撑点选择算法的提升空间,发现优秀支撑点的模式和特征提供数据支撑。然而从n个数据中选择k个支撑点的穷举法的时间复杂度往往高达O(nk+2)。随着n和k的增长,计算代价指数性增长。为了扩大可以精确计算的n和k的范围,需要对穷举算法进行优化。本文的研究包括以下三个方面:（1）提出基于任务重合度和优先计算优秀支撑点的快速支撑点选择穷举算法。并通过MPI和CUDA技术,对支撑点选择穷举算法进行并行化实现。实验证明,快速支撑点选择穷举算法和CUDA并行算法分别具有38以上和近200的加速比。（2）针对实验过程中长期存在的数小时的负载均衡问题,提出了融合work-stealing和多阶段循环神经网络的负载均衡策略（WM-RNN）。实验证明WM-RNN负载均衡策略相较于work-stealing策略有68%以上的性能提升。（3）为了解决算法实现效率低及并行运行参数手动调优耗时问题,提出了基于算法描述模块与搜索空间的HPV算法框架,将常用的算法使用模块化形式表达。随后结合任务重合度概念,提出新的适应性函数,利用遗传算法生成算法优化解。实验证明,HPV框架能在2小时内生成性能接近快速支撑点选择穷举算法的优化方案。本文首先从算法优化及并行设计角度大大提高了支撑点选择穷举算法运行效率,随后提出WM-RNN负载均衡策略,有效地缓解了计算过程中存在的负载不均衡问题,最后提出HPV算法框架,减少了算法实现以及调优时间。本文研究内容为度量空间支撑点选择穷举算法在大数据集上的应用指明了方向。