基于gpu的哈希表建立及其应用

文

I

基于

GPU

的哈希表建立及其应用

哈希技

术

已被广泛

应

用于各个

领

域，如

错误

校正、

语

音

识别

、信息安全、

计

算机密

码

学、

电

子商

务

、病毒

检测

等

领

域，但随着各个

领

域的

发

展，建立哈希表

的速度及数据

查

找速度并不能

满

足需求。近年来

图

形

处

理器

GPU

构架的不断

发

展，以

CUDA

为

代表的

GPU

通用

计

算的普及，在很多

应

用中

获

得几倍、几十倍、

乃至上百倍的加速比，所以利用

CUDA

快速地构建各

类

哈希表并且

应

用于各个

领

域具有重要的

实际

意

义

。

本文以并行建立哈希表算法

为

研究

对

象，

详细

分析了各种建立哈希表的方

法，在充分理解

CUDA

并行原理基

础

上，

实现

了开地址法、

链

地址法、杜

鹃

哈希

法

实时

并行建立哈希表以及

验证说

明

LSH

算法

转

低

维

向量后的保距性，并在此

基

础

上拓展出相关

应

用。在字符串去重

应

用中，核心思想是通

过

字符串哈希函

数聚

类

相同哈希

值

的字符串，再利用并行思想两两字符串精确比

较

，最

终

去掉

在

给

定字符串数据集中重复的字符串。在

纹

理合成

应

用中，核心思想是高

维

相

类

似的向量

经过

LSH

哈希算法

转

低

维

向量后，低

维

向量之

间

能有一定概率地保

证

相似性。在

查

找相似性

KKN

应

用中，核心思想是高

维

向量利用

LSH

算法得到

的低

维

向量后，再

转

化

为

一

维

哈希

值

，再

结

合杜

鹃

哈希建表，最

终

利用杜

鹃

哈希

表

查

找出相似性

KNN

。相比于已有算法，本文工作的

优

点在于利用

CUDA

强

大

的并行能力加速

实现

各

类应

用，挖掘各

类应

用的并行可能，提高运算效率。

本文基于

GPU

分

类讨论

各哈希算法并行建表及其

应

用，主要工作内容如下

：

1.

阐

述开地址哈希法中碰撞

发

生

时

三种不同的

处

理方式，并

针对这

三种不同

处

理方式分

别

在

CPU

平台和

GPU

平台

实现

开地址法建立哈希表，最后

做出两平台的效率

对

比。

2.

阐

述

链

地址哈希法中

处

理碰撞的方式，在

GPU

上通

过链

地址法建

立哈希表，并

应

用于字符串去重；作

为对

比

实验

，在

CPU

上利用

Trie

树实现

字符

串去重，最后

进

行两者之

间

的效率比

较

，以及做出在

GPU

上利用

链

地址法建立

哈希表的

优

缺点分析。

3.

阐

述

LSH

算法与基于像素点的

纹

理合成

TSVQ

算法，并提出用

LS

H

算法

应

用于

纹

理合成，

验证说

明

LSH

算法把高

维

向量

转

低

维

后仍然保距，最

后

进

行

TSVQ

算法与

LSH

算法在

纹

理合成

应

用中的效果的

对

比。

4.

阐

述杜

鹃

哈希法

处

理碰撞的方式，分析串行杜

鹃

哈希建哈希表与

在

GPU

上并行建表的不同，并在

GPU

上

实现

杜

鹃

哈希建立哈希表，最后

结

合

L

SH

算法

实现

近似

KNN

查

找的

应

用。