基于P-稳态分布和空间球面网格的位置敏感哈希算法

摘要

利用数据的相似性对海量数据进行检索是计算机科学中的一个热点研究问题，在多个计算机领域应用广泛。利用数据的相似性进行检索的方法分为两类，最邻近检索和近似最邻近检索。位置敏感哈希算法是一种以概率论和欧几里德几何为理论基础的近似最近邻检索算法。传统的位置敏感哈希算法存在着一些不足，例如传统的位置敏感哈希算法对空间中距离远的数据点的过滤效果有限。而且为了保证算法较高的准确率，需要构建大量的索引表，降低了算法的索引建立效率。为了提出性能更好的解决相似性检索问题的算法，本文在原有的工作上做了以下工作：
　　研究了传统的位置敏感哈希算法，指出了当查询点与数据点距离远时过滤效果差的缺点，针对这个缺点提出两层结构的位置敏感哈希算法。两层位置敏感哈希算法利用空间球面网格将数据集划分成若干有界的子数据集来提高位置敏感哈希算法对距离远的点的过滤效果，同时对数据点的投影区间进行延伸，降低距离近的点被映射到不同区间的概率。计算了两层位置敏感哈希函数的碰撞概率，并给出了两层位置敏感哈希函数的参数的上限。结果显示两层位置敏感哈希函数在误判率和漏判率低于原有的位置敏感哈希函数。利用MATLAB在CIFAR-10数据集的GIST特征库上对两层位置敏感哈希函数做了对比试验，在准确率和召回率上将两层位置敏感哈希函数与现有的位置敏感哈希函数进行对比。
　　针对两层位置敏感哈希算法的结构的特点，设计了分布式哈希索引表。两层分布式索引表结构利用两层位置敏感哈希算法分两步对数据集进行哈希的特点，将索引表设计成两层分布式结构。两层分布式索引表可以有效降低算法进行检索时的内存占用率，提高了算法对海量数据进行检索时的检索效率。本课题使用搜狗实验室2012版本的数据测试集进行实验，并在检索性能方面与其他海量数据检索算法进行了对比分析。对使用了两层哈希索引表的两层位置敏感哈希算法在检索时间、检索准确率和算法可扩展性方面与单层哈希索引表进行了对比实验。实验证明，在对海量数据进行检索时，本文提出的方法拥有良好的可扩展性，并且具有较高的检索准确率和较快的检索速度。

目录

第1章 绪 论

1.1 课题研究背景及意义

1.2 海量数据检索国内外研究现状及分析

1.3 本文主要研究内容

1.4 本文的结构

第2章 位置敏感哈希算法

2.1 引言

2.2 传统哈希与位置敏感哈希比较

2.3 位置敏感哈希函数

2.4 位置敏感哈希算法框架

2.5 本章小结

第3章 两层位置敏感哈希函数

3.1 引言

3.2 两层位置敏感哈希函数构造

3.3两层位置敏感哈希函数碰撞概率计算

3.4 对比实验

3.5本章小结

第4章 基于Hadoop的分布式哈希索引

4.1 引言

4.2 基于Hadoop的分布式索引结构

4.3 分布式哈希索引表构造

4.4 分布式哈希索引表查询

4.5 对比实验

4.6 本章小结

结论

参考文献

声明

致谢