基于GPU的时间序列并行检索算法研究

论文摘要

本文开始总结当前主流的时间序列研究手段,进而归纳相关研究成果,包括高维时间序列的相似性度量方法和数据流的分析与处理技术。之后指出各种方法之间存在的问题,并从中总结出各种算法的优点和缺点,以及解决此类问题的方向。于此同时,基于GPU的高性能并行计算技术在近些年有了突飞猛进的进展,也成为了很多领域提高算法效率的突破口,本文首先分析了基于GPU的并行通用计算的原理,然后分析一些GPU在各个主要领域的成功应用案例,利用图形处理器(GPU)的并行计算能力和较高的内存带宽特性,从而提出一种基于统一设备架构(CUDA)的时间序列模式提取方法和针对数据流时间序列相似性匹配的并行计算方法。对于数据流的处理,有研究者曾经提出过经典的spring算法,但是经典的spring算法存在着过量匹配以及冗余计算的现象。首先分析了已有的对spring算法的改进策略,随后提出基于GPU的数据流处理算法,实验表明,相对于spring算法,本文所提出的算法不仅速度上得到了提升,且很好的解决了过匹配现象。

论文目录

• 摘要
• Abstract
• 引言
• 研究背景
• 时间序列数据挖掘的研究背景
• 基于图形处理器的高性能计算在数据挖掘领域的研究背景
• 本文的主要工作和论文组织结构
• 1 时间序列数据挖掘研究现状
• 1.1 时间序列概念
• 1.2 研究现况
• 1.2.1 一维时间序列
• 1.2.2 高维时间序列
• 1.2.3 数据流时间序列
• 1.3 时间序列相似性度量概述
• 1.3.1 欧氏距离
• 1.3.2 Minkowski距离
• 1.3.3 字符串编辑距离
• 1.3.4 DTW距离
• 1.3.5 LCSS距离
• 1.3.6 测地线距离
• 2 基于多核架构的并行数据挖掘研究现状
• 2.1 多核计算的发展历程
• 2.1.1 CPU多核并行
• 2.1.2 超级计算机、集群与分布式计算
• 2.1.3 CPU+GPU异构并行
• 2.2 CUDA架构模型概述
• 2.2.1 CUDA的发展历史
• 2.2.2 CUDA计算单元
• 2.2.3 CUDA中的warp
• 2.2.4 CUDA中的执行模型
• 2.3 基于GPU的并行数据挖掘算法研究现状
• 2.3.1 关联规则算法的GPU加速策略
• 2.3.2 聚类算法的GPU加速策略
• 2.3.3 分类算法的GPU加速策略
• 3 基于GPU的时间序列相似性并行检索算法研究
• 3.1 研究背景与意义
• 3.2 时间序列的相似性检索
• 3.3 基于GPU的并行时间序列相似性检索算法
• 3.3.1 问题研究背景
• 3.3.2 Parallel-LCSS算法预定义
• 3.3.3 算法原理
• 3.3.4 Parallel-LCSS算法执行步骤
• 3.3.5 算法优化
• 3.4 实验与结果分析
• 3.4.1 实验平台
• 3.4.2 实验结果
• 4 基于GPU的并行数据流时间序列相似性匹配算法
• 4.1 研究背景与意义
• 4.2 数据流的相似性匹配
• 4.2.1 问题定义
• 4.2.2 经典数据流的匹配算法
• 4.3 数据流挖掘算法并行化可行性分析与处理模型
• 4.3.1 数据流挖掘算法的多核并行化可行性分析
• 4.3.2 基于GPU的数据流处理模型
• 4.4 P-LBM数据流相似性检索算法
• 4.4.1 算法原理
• 4.4.2 算法优化
• 4.4.3 P-LBM算法步骤
• 4.4.4 实验
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢