面向大数据的相似度度量的加速研究

发布时间：2017-12-14 21:24

  本文关键词：面向大数据的相似度度量的加速研究

  更多相关文章： 大数据 数据挖掘 相似度度量 动态时间规划 土地移动距离

【摘要】：21世纪以来,随着信息技术的迅猛发展,数据量呈指数级增长,大数据时代已经到来并给人们的生活带来了全方位的改变。图像数据和流数据是大数据中两种最主要的数据形式。这些海量的数据给数据挖掘,尤其是其中的瓶颈,相似度度量带来了新的挑战：高吞吐量,高能量效率和多源性。由于Complementary Metal-Oxide-Semiconductor (CMOS)工艺无法继续提供Central Processing Unit (CPU)吞吐量和能量效率的提升,提升相似度度量的性能成为面向大数据挑战的一个亟待解决的问题。本文从面向架构(数字电路),面向器件(模拟电路)和面向应用(应用领域)三个角度出发,选取针对流数据处理的动态时间规整(Dynamic Time Warping, DTW)和针对图像处理的土地移动距离(Earth Mover's Distance, EMD)这两个典型的相似度度量进行性能加速的研究。首先为了满足流数据挖掘中数据多源性以及高吞吐量的要求,我们提出了一套可扩展,可配置和高能效的基于FPGA的DTW流数据处理架构。该架构能够同时高能效高性能的处理多源流数据。在该架构中,我们选取了kNN算法来处理分类和异常检测等应用。该架构使用了数据表示方法和精度降低技术。通过设计两个环状PE结构,我们实现了DTW和kNN的可扩展性和可配置性。其次为了在具有事务管理和文件管理能力的嵌入式设备System on Chip (SoC)上实现高性能高能效的流数据挖掘,我们提出了一种基于CPU+FPGA异构平台的DTW流数据加速架构。通过充分利用DTW算法的并行性,我们实现了一个可配置的加速架构。上层应用的软件优化主要在硬核CPU上实现,而DTW加速在可编程逻辑上实现。通过软硬件结合,整个系统性能和能量效率达到最优。第三,结合新器件忆阻器我们通过模拟电路实现了DTW计算的加速。在该加速电路中,忆阻器用来同时进行计算和配置。基于忆阻器的计算是一个连续和异步的过程,因此我们提出了两种基于结果预测的优化方法来进一步加速DTW计算。我们对下限优化方法进行了改进,提出了一种提前下限优化算法。我们同时对DTW计算过程进行优化,提出了一种提前终止优化方法。第四,基于CPU+FPGA异构平台,我们提出了一种基于指令集扩展的EMD加速架构。我们首先对EMD算法进行了分析,在识别其瓶颈部分后,设计了专门的扩展指令对其进行加速。相比于已有的硬件加速,该EMD加速架构能够支持的直方图中特征变量数目有1-2个数量级的提升。第五,针对睡姿监测应用,我们对EMD算法进行了面向特定应用的优化。我们提出了一种针对睡姿应用的相似度度量,面向睡姿的土地移动距离(Body-Earth Mover's Distance, BEMD),来对基于压力传感器的睡姿压力图进行睡姿分类。在睡姿分类过程中,BEMD没有提取任何特征。BEMD利用形状描述器首先将睡姿压力图变换成直方图,然后结合EMD和欧式距离对直方图进行相似度计算。我们提出了一个基于倾斜率的分类器对直方图之间的相似度进行处理,进而实现睡姿分类。本文就两种广泛应用于数据挖掘的相似度度量DTW和EMD进入了深入的研究,为相似度度量优化在数字电路,模拟电路和应用领域提供了理论基础。本文的研究成果能提升整个数据挖掘的处理性能,来应对大数据下数据爆炸的挑战。
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】

中国期刊全文数据库 前6条

1 肖宇;于剑;;加权的自适应相似度度量[J];计算机研究与发展;2013年09期

2 张瑞青;马骏;李铁柱;;基于内容的概念格近似自相似度度量[J];计算机时代;2007年11期

3 李中;张铁峰;;不同相似度度量方式的随机数据聚类分析[J];华北电力大学学报(自然科学版);2012年06期

4 朱索格;胡访宇;;基于海量数据的链接预测方法研究[J];电子技术;2014年03期

5 陈会鸽;曹毅;;基于直方图相似度度量的中央空调风管附尘度检测[J];自动化与信息工程;2009年03期

6 ;[J];;年期

中国博士学位论文全文数据库 前1条

1 徐小维;面向大数据的相似度度量的加速研究[D];华中科技大学;2016年

中国硕士学位论文全文数据库 前2条

1 程炜;基于特征学习与相似度度量学习的人脸确认研究[D];湘潭大学;2016年

2 许新亚;基于判决决策的边坡沉降相似度度量方法研究[D];西安科技大学;2016年

，

本文编号：1289417