基于哈希算法的海量多媒体数据检索研究

发布时间：2017-06-10 12:05

  本文关键词：基于哈希算法的海量多媒体数据检索研究，由笔耕文化传播整理发布。

【摘要】：近邻检索问题是机器学习领域的一个基础问题,在信息检索、计算机视觉、数据挖掘等领域中都有着广泛的应用,例如以图搜图、人脸识别、k-means聚类等。近年来,随着互联网的快速发展,海量多媒体数据随之而来。从多媒体数据中抽取出来的特征一般维度较高且稠密。如何对此类特征进行高效检索,成为了当前学术界和工业界炙手可热的研究内容。目前,主流的近邻检索方法包括基于树的方法和基于哈希的方法这两种。其中,许多基于树的近邻检索方法对特征空间进行树结构的划分,其时间复杂度和空间复杂度都以维度d作为指数,所以当维度d变大时,这些方法的效率就受到了限制。相反地,基于哈希算法的近邻检索方法是通过哈希函数(具有相似性保持的特性,即在原始特征空间中相似的两个特征数据在映射到汉明空间后汉明距离也近)将一个d维的特征编码成一个c位(一般地,c《d)的二进制串,并通过汉明排序或者哈希表来进行检索。其中,汉明排序可以使用硬件(XOR)来进行加速,而基于哈希表的检索时间复杂度是O(1),与维度d无关。由于哈希算法具有高计算效率与维度不敏感的优势,其已经引起了众多学者和专家的研究兴趣。围绕基于哈希算法的海量多媒体数据近邻检索方法这一重要问题,本论文开展了以下工作：(1)面向高效检索的哈希函数学习：基于哈希的近邻检索方法是以哈希函数为基础的,一个好的哈希函数应该能使用尽可能短的哈希编码得到相对较高的准确率。基于随机投影的哈希算法不考虑数据的分布,需要较长位数的二进制串才能获得较好的近似性能。而基于学习的哈希算法从数据的分布中学习出投影向量,能在较短位数的二进制串下获得较好的性能。我们从衡量哈希函数的优劣标准出发,提出了一种基于学习的哈希算法一互补投影哈希算法。其是一个既保持数据的近邻性质(保证检索准确率),又考虑哈希桶均衡性(保证检索速度)的哈希函数学习方法。该算法的提出为基于哈希的高效检索奠定了基础。(2)跨媒体数据的哈希函数学习：海量多媒体(文本、图像、视频、音频等)数据的出现,使得面向跨媒体数据的哈希函数学习变得尤为重要。其要求学习出的哈希函数能够使不同媒体之间的关联体现在哈希编码中,即具有相同概念的多媒体数据在编码后应具有相同的二进制串。为此,我们提出了迭代多视角(Multi-View)哈希算法。其是一个同时保持同模态相似性和跨模态相似性的跨媒体哈希函数学习方法。其中,相似性的保持不止体现在对于相似数据要拥有相似的哈希编码,也体现在不相似数据要拥有不相似的哈希编码(独特性)。该算法的提出为跨媒体数据的哈希函数学习提供了一个良好的优化框架。(3)优化的基于哈希表结构的快速近邻检索：目前,相比基于树结构的近邻检索方法,基于哈希表的近邻检索方法未能展现出明显的优势。其主要原因在于目前的哈希算法为了达到高准确率和高召回率,通常需要扩展汉明半径来进行搜索,这使得检索时间大大增加。为了消除这个瓶颈,我们提出了迭代扩展哈希算法,其在线上使用一个辅助索引来对使用小汉明半径检索到的点做迭代扩展,以此来保证高准确率、高召回率和低检索时间。该算法从本质上提升了基于哈希表的近邻检索性能,为线上海量数据的实时搜索提供了有力保障。
【关键词】：大数据 近邻检索 哈希算法
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP181
【目录】：

• 摘要5-7
• Abstract7-15
• 1 绪论15-21
• 1.1 研究背景和意义15-17
• 1.1.1 研究背景15-17
• 1.1.2 研究意义17
• 1.2 论文的研究内容和目标17-19
• 1.2.1 研究内容17-18
• 1.2.2 研究目标18-19
• 1.3 论文的组织结构19-21
• 2 海量多媒体数据检索研究现状21-33
• 2.1 近邻检索问题21-22
• 2.2 基于树结构的近邻检索方法22-23
• 2.2.1 KD树22
• 2.2.2 聚类树22-23
• 2.2.3 其它树结构23
• 2.3 基于哈希的近邻检索方法23-31
• 2.3.1 局部敏感哈希24
• 2.3.2 单模态哈希算法24-30
• 2.3.3 多模态哈希算法30-31
• 2.4 基于kNN图的近邻搜索方法31
• 2.5 本章小结31-33
• 3 面向高效检索的互补投影哈希算法33-47
• 3.1 引言33-35
• 3.2 与相关工作的区别35
• 3.3 算法35-41
• 3.3.1 穿越数据的稀疏区域35-36
• 3.3.2 近似均衡的哈希桶36-38
• 3.3.3 目标函数38-39
• 3.3.4 谱松弛39
• 3.3.5 梯度下降39-40
• 3.3.6 计算复杂度分析40-41
• 3.4 实验41-45
• 3.4.1 数据集41-42
• 3.4.2 实验设置42-43
• 3.4.3 比较的哈希算法43
• 3.4.4 实验结果与分析43-45
• 3.5 本章小结45-47
• 4 面向跨媒体数据索引的迭代多视角哈希算法47-65
• 4.1 引言47-48
• 4.2 记号48
• 4.3 算法48-53
• 4.3.1 视角内相似性保持48-49
• 4.3.2 视角间的相似性保持49-50
• 4.3.3 目标函数50-51
• 4.3.4 优化方法51-53
• 4.4 实验53-63
• 4.4.1 数据集54
• 4.4.2 实验设置54-55
• 4.4.3 比较的方法55-56
• 4.4.4 Wiki上的跨模态检索结果56-57
• 4.4.5 Flickr上的跨模态检索结果57-58
• 4.4.6 Flickr上的单模态检索结果58-59
• 4.4.7 训练效率59-61
• 4.4.8 参数敏感性61-62
• 4.4.9 收敛速度62-63
• 4.5 本章小结63-65
• 5 基于迭代扩展哈希算法的优化哈希表索引65-81
• 5.1 引言65-66
• 5.2 记号66
• 5.3 算法66-70
• 5.3.1 算法流程66-67
• 5.3.2 kNN表的动态更新67-68
• 5.3.3 线上阶段的实现68-69
• 5.3.4 理论分析69-70
• 5.3.5 复杂度分析70
• 5.4 实验70-79
• 5.4.1 数据集71
• 5.4.2 实验设置71-72
• 5.4.3 与原始哈希方法的比较72-76
• 5.4.4 与多哈希表LSH的比较76-77
• 5.4.5 与KD树的比较77-78
• 5.4.6 时间复杂度78-79
• 5.4.7 参数选择79
• 5.5 本章小结79-81
• 6 总结与展望81-83
• 6.1 本文工作总结81-82
• 6.2 工作展望82-83
• 参考文献83-97
• 攻读博士学位期间主要的研究成果97-99
• 致谢99

【相似文献】

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

1 陈一骄;卢锡城;孙志刚;;面向流管理的哈希算法研究[J];计算机工程与科学;2008年04期

2 邹保平;;基于一致哈希算法的用电信息采集系统研究[J];电力信息化;2011年06期

3 刘华珠;贺前华;;基于哈希算法的网络桥接器地址维护方法(英文)[J];科学技术与工程;2008年17期

4 王远;;可重构哈希算法芯片的设计与实现[J];电脑知识与技术;2012年04期

5 张江,傅鹤岗;基于关联规则的二维哈希算法的改进[J];计算机工程与设计;2005年08期

6 唐铭;史长琼;周恺卿;张大方;;倒插入分段哈希算法[J];计算机应用;2011年02期

7 孙阳;朱宏峰;刘天华;;一种新型抗旋转攻击的鲁棒哈希算法[J];小型微型计算机系统;2011年04期

8 贺贤明,邵雷兵;一种基于学习的自适应哈希算法研究[J];计算机应用与软件;2004年11期

9 邵雷兵,庄毅;一种基于学习的自适应哈希算法研究[J];微电子学与计算机;2004年08期

10 陈青华;;一种新型的图像哈希算法[J];兵工自动化;2011年05期

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

1 刘宗斌;马原;荆继武;夏鲁宁;;SM3哈希算法的硬件实现与研究[A];第26次全国计算机安全学术交流会论文集[C];2011年

2 文振q;朱为总;欧阳杰;高金花;;一种鲁棒可区分的视频感知哈希算法[A];第18届全国多媒体学术会议（NCMT2009）、第5届全国人机交互学术会议（CHCI2009）、第5届全国普适计算学术会议（PCC2009）论文集[C];2009年

3 文振q;高金花;刘朋飞;杜以华;张萌;;基于分块DCT和PCA的图像感知哈希算法研究[A];第十五届全国图象图形学学术会议论文集[C];2010年

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

1 金仲明;基于哈希算法的海量多媒体数据检索研究[D];浙江大学;2015年

2 焦玉华;音频感知哈希算法研究[D];哈尔滨工业大学;2010年

3 赵玉鑫;多媒体感知哈希算法及应用研究[D];南京理工大学;2009年

4 赵杠;对偶连接问题的哈希算法研究[D];复旦大学;2010年

5 胡媛媛;基于视觉模型的图像感知哈希算法研究[D];哈尔滨工业大学;2011年

6 袁鑫攀;基于minwise哈希的文档复制检测的研究及应用[D];中南大学;2012年

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

1 史世泽;局部敏感哈希算法的研究[D];西安电子科技大学;2013年

2 林悦;基于哈希算法的高维数据的最近邻检索[D];浙江大学;2013年

3 翁新钎;安全哈希算法的并行化实现研究[D];复旦大学;2013年

4 张培超;基于隐变量模型的监督式哈希算法[D];上海交通大学;2014年

5 刘水生;感知哈希算法基准测试平台研究与设计[D];哈尔滨工业大学;2008年

6 周权;面向嵌入式安全哈希算法的研究与实现[D];湖南大学;2013年

7 孙守兴;基于可扩展哈希算法的并行爬虫动态负载均衡实现[D];哈尔滨工业大学;2010年

8 周建辉;基于半监督哈希算法的图像检索方法研究[D];大连理工大学;2011年

9 曹姣;位置敏感哈希算法的性能分析研究[D];东华大学;2014年

10 吕月明;基于非对称哈希算法的大规模图像检索的研究[D];华南理工大学;2015年

  本文关键词：基于哈希算法的海量多媒体数据检索研究，由笔耕文化传播整理发布。

，

本文编号：438404