面向大规模数据相似计算和搜索的哈希方法研究

发布时间：2017-05-30 09:00

  本文关键词：面向大规模数据相似计算和搜索的哈希方法研究，，由笔耕文化传播整理发布。

【摘要】：互联网的发展带来了数据的爆炸式增长。如何在大规模数据中做基于相似度的计算和搜索是一个有广阔应用背景且具有挑战性的基础问题,而具有局部敏感性质的哈希方法则是一个有力的工具。局部敏感哈希方法将数据压缩成紧凑的哈希码,通过计算哈希码间的某种简单距离(比如海明距离)即可快速估计出原始数据对间的相似度或者距离。这种保相似度的哈希码作为对数据的一种压缩表示,可以作为各种基于相似度的机器学习和数据挖掘算法的输入,从而实现了存储上的压缩和计算上的加速。另一方面,也可以建立哈希表实现快速的相似搜索。目前有各种局部敏感哈希方法针对不同的数据类型和相似度定义。现有的局部敏感哈希方法的估计方差较大,需要计算较多的哈希函数以保证一定的估计精度,从而带来了较大的计算和存储开销。本文首先针对具有简单结构的数据——向量和集合,研究了相应的局部敏感哈希方法。相对于局部敏感哈希使用独立采样的哈希函数,本文提出使用结构化采样的哈希函数,以降低估计的方差或者哈希时间。另一方面,之前的研究大多针对简单结构的数据,而很多实际数据并不能用简单结构来表示,比如子空间、图等。本文针对具有子空间结构的数据提出了一种局部敏感哈希方法,并推广到了三阶张量类型的数据上。本文的创新点包括:1、针对向量类型的数据,本文提出了超比特局部敏感哈希,使用结构化采样的哈希函数——分组正交化的随机投影向量构成的哈希函数,作为对符号随机投影哈希的改进。本文证明了超比特局部敏感哈希可以提供对向量间角度的无偏估计,并在理论上研究了由分组正交随机投影向量构成的哈希函数所带来的方差的降低。实验验证了理论结果;2、对于集合类型的数据,本文提出了最小最大值哈希方法,采用结构化的哈希函数——最小值函数和最大值函数,作为对最小值哈希的改进。本文证明了最小最大值哈希在保证无偏估计的基础上,将哈希时间降低到最小值哈希的一半,并且方差也略有降低;实验验证了理论结果;3、本文针对子空间和三阶张量类型的数据,提出了子空间保角哈希,并进行了理论分析和实验验证。本文还提出了快速符号随机投影方法和双线性随机投影方法用于加速子空间保角哈希的计算。
【关键词】：局部敏感哈希 海明距离 相似搜索
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.3
【目录】：

• 摘要3-4
• Abstract4-8
• 第1章 研究背景8-15
• 1.1 局部敏感哈希介绍9-11
• 1.1.1 局部敏感哈希函数族9-10
• 1.1.2 若干局部敏感哈希函数族简介10-11
• 1.2 局部敏感哈希研究概述11-12
• 1.3 论文结构12-15
• 第2章 超比特局部敏感哈希15-49
• 2.1 研究动机15-16
• 2.2 相关研究16-18
• 2.3 符号随机投影哈希18-20
• 2.4 超比特局部敏感哈希20-22
• 2.5 理论分析22-39
• 2.5.1 无偏估计22-24
• 2.5.2 方差分析24-37
• 2.5.3 数值验证实验37-39
• 2.6 实验39-45
• 2.6.1 角度估计39-42
• 2.6.2 近似近邻搜索42-45
• 2.7 本章总结45-49
• 第3章 最小最大值哈希49-71
• 3.1 研究动机49-50
• 3.2 最小值哈希和K-最小值哈希50-55
• 3.2.1 最小值哈希50-54
• 3.2.2 K-最小值哈希54-55
• 3.3 关于最小值哈希和K-最小值哈希的方差分析55-57
• 3.3.1 K-最小值哈希的方差分析56-57
• 3.3.2 讨论57
• 3.4 最小最大值哈希57-66
• 3.4.1 哈希时间分析60-61
• 3.4.2 估计的无偏性61
• 3.4.3 方差分析61-63
• 3.4.4 扩展63-66
• 3.5 实验66-70
• 3.5.1 数据集66-67
• 3.5.2 杰卡德相似度估计67-68
• 3.5.3 近似近邻搜索68-70
• 3.6 本章总结70-71
• 第4章 子空间保角哈希71-95
• 4.1 研究动机71-73
• 4.2 相关研究73
• 4.3 子空间的相似度定义73-76
• 4.3.1 子空间之间的主角73-74
• 4.3.2 子空间的角度、角度相似度和角度距离74-76
• 4.4 保持角度相似度的子空间哈希方法76-81
• 4.5 加速随机投影的计算81-86
• 4.5.1 快速符号随机投影81-84
• 4.5.2 双线性随机投影84-86
• 4.6 实验86-93
• 4.6.1 人脸识别86-90
• 4.6.2 手势和动作识别90-93
• 4.7 本章总结93-95
• 第5章 总结与展望95-99
• 参考文献99-105
• 致谢105-107
• 个人简历、在学期间发表的学术论文与研究成果107

【相似文献】

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

1 张勇,雷振明;基于流应用中的哈希查表性能研究[J];计算机工程与应用;2003年25期

2 马如林;蒋华;张庆霞;;一种哈希表快速查找的改进方法[J];计算机工程与科学;2008年09期

3 蒋大宏;动态哈希方法[J];计算机工程;1993年01期

4 蒋大宏;实现检索代价最优的动态哈希法[J];计算机工程与应用;1994年Z2期

5 刘冠福;;动态哈希表的设计及应用[J];计算机时代;1996年02期

6 朱芳芳;李训根;;改进的哈希表查找算法[J];杭州电子科技大学学报;2013年05期

7 赵宇;;基于哈希表查找方法的优势及其算法的改进[J];中小企业管理与科技(下旬刊);2012年03期

8 高文利;朱丽;;哈希表在计算语言学中的运用[J];现代语文(语言研究版);2009年06期

9 贺元香;史宝明;;除留余数法建立哈希表的方法改进[J];甘肃科技;2008年07期

10 刘舱强;邓昌胜;余谅;;基于哈希表的最长前缀匹配算法改进[J];微计算机信息;2009年30期

中国重要会议论文全文数据库 前2条

1 朱芳芳;李训根;;改进的哈希表查找算法[A];浙江省电子学会2013学术年会论文集[C];2013年

2 赵竞;余宏亮;张X;郑纬民;;广域网分布式哈希表存储副本可靠性的维护[A];全国网络与信息安全技术研讨会论文集（下册）[C];2007年

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

1 黄慧群;内容中心网络的查表技术研究[D];解放军信息工程大学;2014年

2 季剑秋;面向大规模数据相似计算和搜索的哈希方法研究[D];清华大学;2015年

3 彭建章;非阻塞算法与多进程网络程序优化研究[D];中国科学技术大学;2013年

4 付海燕;基于图像哈希的大规模图像检索方法研究[D];大连理工大学;2014年

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

1 郝广洋;语音感知哈希及其在密文语音检索中的应用研究[D];西南交通大学;2015年

2 黄志骞;基于迭代量化的用于近似最近邻检索的哈希方法[D];华南理工大学;2015年

3 王聪;基于局部敏感哈希的声源定位方法[D];大连理工大学;2015年

4 邓慧茹;面向大规模视觉检索的哈希学习[D];西安电子科技大学;2014年

5 张梁;基于局部敏感哈希的近似近邻查询算法研究[D];南京邮电大学;2015年

6 卢佳音;基于图像哈希检索的图像重排方法研究[D];大连理工大学;2013年

7 汪龙重;达梦数据库哈希连接算法的研究[D];华中科技大学;2012年

8 杨牧洲;分层哈希链表及其在数据查询认证中的应用[D];东北大学;2009年

9 陈凯;数据库哈希连接算法研究[D];复旦大学;2013年

10 李洋;基于自学哈希的信息检索[D];吉林大学;2015年

  本文关键词：面向大规模数据相似计算和搜索的哈希方法研究，由笔耕文化传播整理发布。

本文编号：406756