海量高维数据的多哈希表索引算法的研究

摘要

近年来，随着互特网技术的快速发展，多媒体数据诸如文本、图像、视频等数据已呈现爆炸性增长的趋势。如何在海量的多媒体数据中搜索到目标数据是计算机科学研究领域的一个热点问题。由于在实际应用中，多媒体数据一般通过其特征数据表示，而这些特征表示往往是高维向量数据。此时传统的基于空间划分树、聚类划分树等索引技术的检索方案，并不能很好地应对这类海量高维数据，且面临着效率低下的问题。
　　针对海量高维数据的近邻查询，一种主流的解决思路是把数据映射为二进制码，其主要原因是二进制码具备存储代价低、汉明距离计算快等特性。主流的研究工作包括局部敏感哈希、乘积量化、ITQ、K均值哈希等。不过，二进制表示本身也有一些问题:首先，如何使得二进制码表示能够保持原始数据之间的空间近邻结构;其次，如何利用尽量少的二进制码位数来保持尽量高的检索性能;再次，当数据的规模太大直接进行汉明距离匹配效率过低时，如何利用二进制码作为索引，给出海量高维数据的高效索引及查询方案等。
　　针对海量高维数据的二进制表示如何索引问题，本文提出了一种新的索引结构及近邻查找算法，即基于多哈希表的索引及查询算法。首先，通过度量不同哈希位之间的独立性，选择最优的哈希位分组方案。由于哈希位之间的组合数是几何数量级的，提出了近似求解的方法来构建多个哈希表。其次，对于原始数据集中的数据点，进行离线索引的构建。再次，对于给定查询点，在多个哈希表中分别搜索查询点近邻，并提出了近邻查询扩展和优化方法。最后，结合当前主流的大数据计算框架Spark，讨论了算法的并行实现。
　　为了评价多哈希表索引及查询算法的性能，在多个数据集包括公开数据集和合成数据集上，进行了大量的数值实验，并且和一些主流的哈希及索引算法进行了对比分析。数值实验说明，相比于其它算法，论文提出的算法在检索的准确率、召回率、MAP值方面具备一定的优势。

目录

声明

摘要

第1章 绪论

1．1 课题研究的背景及意义

1．2 国内外研究现状

1．3 论文的主要工作及组织结构

1．4 本章小结

第2章 相关技术介绍

2．1 传统索引技术

2．1．1 空间划分树索引及近邻查询

2．1．2 聚类划分树索引及近邻查询

2．2 局部敏感哈希

2．2．1 汉明距离

2．2．2 LSH定义

2．3 乘积量化算法

2．3．1 矢量量化

2．3．2 乘积量化

2．3．3 优化的乘积量化

2．4 分布式计算框架

2．4．1 Hadoop

2．4．2 Spark

2．5 本章小结

第3章 基于多哈希表索引的近邻查找算法

3．1 问题描述

3．2 论文方法的提出

3．3 多哈希表的建立

3．3．1 二进制编码表示

3．3．2 不同哈希位关联性的衡量

3．3．3 比特位分组方案的优化

3．4 数据的索引及查询优化

3．5 Spark并行环境的实现

3．5．1 数据及任务并行化

3．5．2 Spark的并行实现

3．6 本章小结

第4章 实验设计与结果分析

4．1 实验环境及数据库

4．1．1 实验环境

4．1．2 实验数据

4．2 算法的评估标准

4．3 实验结果与分析

4．3．1 哈希表哈希位数的影响

4．3．2 不同方法的对比实验

4．4 本章小结

第5章 总结与展望

参考文献

攻读学位期间公开发表论文

致谢