基于学习的分布式局部敏感哈希算法研究

摘要

随着计算机网络技术的不断发展，网络中充斥着各种各样的海量高维数据，在此数据中搜索目标数据也随之变得耗时和低效。为解决上述问题，近似近邻搜索的概念及各种算法被陆续提出，并成为机器学习、数据挖掘、模式识别等多种应用中的一类基本算法，而局部敏感哈希算法被证明是解决高维空间近邻搜索的最有效算法之一。
　　在处理大数据问题上，基于(key，value)的分布式结构被越来越广泛的采用，如经典的并行编程框架MapReduce、Twitter Storm和Spark等。结合(key，value)结构，对经典局部敏感哈希算法进行分布式化，是近期的研究热点。为了保证查询精度，需要建立大量的哈希表，这无疑将占用不少内存空间，尤其是在处理高维数据的场合。同时，在分布式背景下，由于哈希桶位于不同的节点，在不同的哈希桶进行查询就会产生多次网络调用，从而导致大量的网络传输。为了减少内存占用和网络调度费用，Layered LSH给出了采用O(1)个哈希表的分布式局部敏感哈希方案。不过，研究中发现会降低查询的精度。
　　本文尝试设计了一种将学习算法应用在基于(key，value)的分布式结构，且在该索引基础上进行了基于MapReduce的空间近邻查询实现。本文的主要工作如下:(1)提出了查询精度更高的算法LB-LSH，改进了Entropy LSH的分布式(key，value)模型。(2)类似于Layered LSH机制，LB-LSH在采用O(1)个哈希表的情况下保证了查询精度，大大减少了网络传输和频繁的I/O。(3)在Hadoop平台上实现了LB-LSH，大量的实验结果显示，该算法优于当前所采用的一些哈希算法。

目录

声明

摘要

第1章 绪论

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

1．2 国内外研究现状

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

第2章 相关技术介绍

2．1 云计算和MapReduce

2．1．1 云计算概述

2．1．2 MapReduce编程模型及运行原理

2．1．3 Hadoop MapReduce实现

2．2 聚类算法

2．2．1 k-means聚类算法介绍

2．2．2 k-means的MapReduce实现

2．3 局部敏感哈希算法

2．3．1 局部敏感哈希算法

2．3．2 Entropy LSH的介绍

2．3．3 Layered LSH的介绍

2．3．4 DSH的介绍

2．4 本章小结

第3章 基于学习的分布式局部敏感哈希算法

3．1 分布式局部敏感哈希的实现

3．2 LB-LSH

3．2．1 二层索引技术的实现

3．2．2 哈希家族的创建

3．3 时间复杂度分析

3．3．1 预处理时间复杂度

3．3．2 网络调用复杂度分析

3．4 本章小结

第4章 实验结果与分析

4．1 实验环境配置

4．1．1 实验平台的搭建

4．1．2 实验数据集

4．2 实验对比方案

4．3 实验实现细节

4．4 实验结果

4．4．1 调控查询点偏移量L

4．4．2 敏感参数D的调控

4．5 本章小结

第5章 总结与展望

5．1 工作总结

5．2 研究展望

参考文献

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

致谢