第一章 绪论
1.1研究的背景及研究现状
本章详细地叙述了在高维空间中相似性查询技术的研究背景和研究现状，然后阐述了本文的研究目标和研究内容，最后介绍了本文的组织架构。
1.1.1 研究背景
近年来，随着信息技术的快速发展，通过网络获取信息已经成为人们生活中不可或缺的一部分。另外，由于多媒体设备以及便携式记录仪的快速普及，越来越多的人们参与到数据的生产和流通过程，这样就促使信息数据呈现爆炸式的增长。面对庞大而且纷繁复杂的视频或者图像等数据，如何查询出有用的信息面临极大的挑战。
在信息检索领域，海量的数据是重要的研究对象。特别是处于这样一个大数据的时代，数据的相似性查询更是一个重要的研究课题。在通常情况下，给定待查询的数据点，通过某种距离度量方式计算之后，从数据库中快速而准确地返回与待查询数据点相似的数据点这一过程，我们把它称作相似性查询[1]。事实上，除了以上领域用到相似性查询，这项技术还被广泛的应用到其他计算机领域，包括信号处理、机器学习、数据挖掘等[2]。 传统的相似性图像查询算法大多是最近邻搜索（Nearest Neighbor，NN）方法[3]。最近邻搜索方法又称为暴力搜索（Brute Force）算法，其选取一种距离计算公式在数据库中查找与待查询对象距离最近的样本，其查询的时间复杂度是 ? ?O n ，即与样本数量呈线性关系。当数据量很大时，查询效率急剧下降。为了节约查询时间，如果在不需要完全精确查询结果的情况下，只要找到待查询数据点的近似结果即可满足数据查询的需求，也就是说允许查询到的结果和真实的查询结果存在一定的误差。基于这样的思想，近似近邻（Approoximate Nearest Neighbor，ANN）算法[4]被提出，并且在信息检索、目标识别和数据分类等计算机视觉领域得到了大量的应用[5]。
近年来，随着信息技术的快速发展，通过网络获取信息已经成为人们生活中不可或缺的一部分。另外，由于多媒体设备以及便携式记录仪的快速普及，越来越多的人们参与到数据的生产和流通过程，这样就促使信息数据呈现爆炸式的增长。面对庞大而且纷繁复杂的视频或者图像等数据，如何查询出有用的信息面临极大的挑战。
在信息检索领域，海量的数据是重要的研究对象。特别是处于这样一个大数据的时代，数据的相似性查询更是一个重要的研究课题。在通常情况下，给定待查询的数据点，通过某种距离度量方式计算之后，从数据库中快速而准确地返回与待查询数据点相似的数据点这一过程，我们把它称作相似性查询[1]。事实上，除了以上领域用到相似性查询，这项技术还被广泛的应用到其他计算机领域，包括信号处理、机器学习、数据挖掘等[2]。 传统的相似性图像查询算法大多是最近邻搜索（Nearest Neighbor，NN）方法[3]。最近邻搜索方法又称为暴力搜索（Brute Force）算法，其选取一种距离计算公式在数据库中查找与待查询对象距离最近的样本，其查询的时间复杂度是 ? ?O n ，即与样本数量呈线性关系。当数据量很大时，查询效率急剧下降。为了节约查询时间，如果在不需要完全精确查询结果的情况下，只要找到待查询数据点的近似结果即可满足数据查询的需求，也就是说允许查询到的结果和真实的查询结果存在一定的误差。基于这样的思想，近似近邻（Approoximate Nearest Neighbor，ANN）算法[4]被提出，并且在信息检索、目标识别和数据分类等计算机视觉领域得到了大量的应用[5]。
................................
1.2 论文研究目标及内容
1.2.1 研究目标
局部敏感哈希算法将高维空间中的数据点映射到低维空间后仍然可以保持数据点的相似性，可以有效地解决高维数据的近似近邻搜索问题。结构化分布式的 P2P 网络在数据空间中消除了集中式系统的单点瓶颈，具有高扩展性、鲁棒性等特点。本文的研究目标是保证海量高维图像在分布式系统中的负载均衡，充分利用局部敏感哈希算法的性质和结构化 P2P 分布式索引系统的特点，以哈希数据的分布静态模型为支撑，将海量数据均衡地映射到分布式系统的节点上，分析并设计了一种基于 LSH 的静态分布式相似性检索机制。研究基于 P2P 分布式网络的动态负载均衡方法，提出了一种基于虚拟节点的动态负载均衡算法。本文通过实现分布式网络负载的均衡性和检索结果的高质量与全面性，使海量高维图像数据的潜在价值得以充分的发挥与增值。
1.2.21.2.2 研究内容
（1） 基于 LSH 的分布式索引数据分布模型的研究
由于高维数据带来的“维度灾难”和存储空间等问题，无法准确的构建数据分布索引模型。本文在高维空间中构建了基于单张哈希表的数据分布索引模型，能够很好地预测高维数据点的分布，并且显著显著减少创建分布式索引占据的空间。
（2） 静态分布式相似性图像索引负载均衡机制的研究
面对海量的高维数据点，传统的分布式相似性图像索引机制会遭遇负载不均衡问题，不均衡的负载网络影响整个网络的查询效率。本文在基于 LSH 的分布式索引数据分布模型的基础上，研究了一种静态分布式相似性图像索引负载均衡机制，能够在概率上保证在数据映射阶段每个节点的负载均衡。
（3） 基于虚拟节点的动态负载均衡算法研究
分布式 P2P 网络中的节点会因为失效或其它原因动态性地加入或者离开网络，这些网络结构变化等原因会造成节点负载的不均衡。为了实现动态地调整节点负载，本文研究了一种基于虚拟节点概念的的动态负载均衡算法，在类似 Chord 的 P2P 网络中能够实现节点负载的动态性调整。
...........................
第二章 相关技术和理论知识介绍
2.1 相似性搜索
2.1.1相似性索引的定义
相似性搜索是指对于给定的待查询数据对象，通过某种度量方式计算之后，从数据库中返回在距离上与待查询数据相近的数据对象[35]。
在计算机科学领域中，这些图像数据对象通常被表示为点，即空间向量。将相似性的图像搜索问题就转化为空间向量的相似性搜索问题，而向量之间的相似性一般是通过某种相似性度量方式来衡量。接下来我们首先介绍相似性索引的度量方法。
1.2 论文研究目标及内容
1.2.1 研究目标
局部敏感哈希算法将高维空间中的数据点映射到低维空间后仍然可以保持数据点的相似性，可以有效地解决高维数据的近似近邻搜索问题。结构化分布式的 P2P 网络在数据空间中消除了集中式系统的单点瓶颈，具有高扩展性、鲁棒性等特点。本文的研究目标是保证海量高维图像在分布式系统中的负载均衡，充分利用局部敏感哈希算法的性质和结构化 P2P 分布式索引系统的特点，以哈希数据的分布静态模型为支撑，将海量数据均衡地映射到分布式系统的节点上，分析并设计了一种基于 LSH 的静态分布式相似性检索机制。研究基于 P2P 分布式网络的动态负载均衡方法，提出了一种基于虚拟节点的动态负载均衡算法。本文通过实现分布式网络负载的均衡性和检索结果的高质量与全面性，使海量高维图像数据的潜在价值得以充分的发挥与增值。
1.2.21.2.2 研究内容
（1） 基于 LSH 的分布式索引数据分布模型的研究
由于高维数据带来的“维度灾难”和存储空间等问题，无法准确的构建数据分布索引模型。本文在高维空间中构建了基于单张哈希表的数据分布索引模型，能够很好地预测高维数据点的分布，并且显著显著减少创建分布式索引占据的空间。
（2） 静态分布式相似性图像索引负载均衡机制的研究
面对海量的高维数据点，传统的分布式相似性图像索引机制会遭遇负载不均衡问题，不均衡的负载网络影响整个网络的查询效率。本文在基于 LSH 的分布式索引数据分布模型的基础上，研究了一种静态分布式相似性图像索引负载均衡机制，能够在概率上保证在数据映射阶段每个节点的负载均衡。
（3） 基于虚拟节点的动态负载均衡算法研究
分布式 P2P 网络中的节点会因为失效或其它原因动态性地加入或者离开网络，这些网络结构变化等原因会造成节点负载的不均衡。为了实现动态地调整节点负载，本文研究了一种基于虚拟节点概念的的动态负载均衡算法，在类似 Chord 的 P2P 网络中能够实现节点负载的动态性调整。
...........................
第二章 相关技术和理论知识介绍
2.1 相似性搜索
2.1.1相似性索引的定义
相似性搜索是指对于给定的待查询数据对象，通过某种度量方式计算之后，从数据库中返回在距离上与待查询数据相近的数据对象[35]。
在计算机科学领域中，这些图像数据对象通常被表示为点，即空间向量。将相似性的图像搜索问题就转化为空间向量的相似性搜索问题，而向量之间的相似性一般是通过某种相似性度量方式来衡量。接下来我们首先介绍相似性索引的度量方法。
在相似性索引领域，对于一个给定的待查询数据对象，需要到通过相似性索引算法构建的索引结构中查询数据对象然后返回最终的查询结果。在起初构建数据对象索引的时候，对于不同的应用场景和不同的数据集，相似性索引结构就定义了从数据库中返回的查询结果应该满足的不同条件。按照返回的查询结果精度的不同，我们把相似性查询分为精确查询和近似查询，而相对应的相似性查询算法称之为最近邻（Nearest Neighbor，NN）查询算法和近似最近邻（Approximate Nearest Neighbor，ANN）查询算法[44-46]。
最近邻查询即从数据库中搜索到与待查询的数据对象最相近的数据点，一般也用它来表示精确查询，也被称作线性查询或者暴力搜索。这种方法是在给定数据集和相似性度量方式的前提下，严格按照距离大小返回特定的查询结果以满足精确查询的精度要求。范围查询和K 近邻查询是两种常见的查询方式[47]。
最近邻查询即从数据库中搜索到与待查询的数据对象最相近的数据点，一般也用它来表示精确查询，也被称作线性查询或者暴力搜索。这种方法是在给定数据集和相似性度量方式的前提下，严格按照距离大小返回特定的查询结果以满足精确查询的精度要求。范围查询和K 近邻查询是两种常见的查询方式[47]。
.........................
2.2局部敏感哈希算法
2.2.1 LSH 原理
局部敏感哈希算法是解决高维空间中近似近邻搜索的经典算法，因其良好的搜索效率和维度适应性而被广泛的应用信息检索等各个领域。LSH 的基本思想如下：利用哈希函数（Hash Function）对数据集中的所有数据点进行哈希操作，使得距离相近点的冲突概率大于距离远的点的冲突概率[7]。换句话说，相似的数据点被哈希到同一个桶的概率大于不相似的数据点。在执行查询操作时，将查询的数据点按照相同的操作哈希到桶中，然后取出该桶中的所有点作为候选集，计算查询点和每个候选集之间的距离，最后返回符合查询条件的数据点。
由于使用哈希函数对整个数据集进行了过滤，可以获取可能满足查询条件的数据点，然后再通过距离计算公式进一步筛选，这样就可以必选查询点与数据集中所有的数据点逐一进行计算，提高了搜索的效率。
.............................
2.2局部敏感哈希算法
2.2.1 LSH 原理
局部敏感哈希算法是解决高维空间中近似近邻搜索的经典算法，因其良好的搜索效率和维度适应性而被广泛的应用信息检索等各个领域。LSH 的基本思想如下：利用哈希函数（Hash Function）对数据集中的所有数据点进行哈希操作，使得距离相近点的冲突概率大于距离远的点的冲突概率[7]。换句话说，相似的数据点被哈希到同一个桶的概率大于不相似的数据点。在执行查询操作时，将查询的数据点按照相同的操作哈希到桶中，然后取出该桶中的所有点作为候选集，计算查询点和每个候选集之间的距离，最后返回符合查询条件的数据点。
由于使用哈希函数对整个数据集进行了过滤，可以获取可能满足查询条件的数据点，然后再通过距离计算公式进一步筛选，这样就可以必选查询点与数据集中所有的数据点逐一进行计算，提高了搜索的效率。
.............................
第三章 基于 LSH 的分布式相似性图像索引负载均衡机制 ................................ 25
3.1引言 ................................... 25
3.2基于 LSH 的数据分布模型的构建 .................................. 26
第四章 基于虚拟节点的动态负载均衡算法 ....................... 39
4.1引言 ............................................... 39
4.2负载网络模型 .................................. 39
第五章 实验评估 ........................................ 46
5.1数据集介绍 .................................. 46
5.2实验设置 ......................................... 46
第五章 实验评估
5.1 数据集介绍
针对数据点查询问题，给出两个可行的方法：（i）线性查询方法和（ii）多探针查询方法。线性查询方法是是按照当前节点的后继方向进行线性查询。为了获取理想的查询结果，可以通过设置查询跳数和后继节点的数量来进行控制。另外，由于 Multi-probe LSH 算法中可以轻微地改变哈希桶的索引值，从而获取与当前哈希桶标识符相近的数据点。我们可以利用这种思想产生与当前查询节点索引值相近的节点标识符。考虑到最大的待探测的探针数量和重复访问的问题，可以先产生一个与当前节点相近的索引值集合，然后通过对这个集合中的索引值作判断，如果当前产生的索引值已经被访问过了，就可以从索引值集合中去除这个节点标识符，再访问其他的节点标识符。通过设置最大探针的数量，可以避免过多冗余的查询操作。
.............................
第六章 总结和展望
6.1工作总结
相似性搜索在信息检索等领域有着广泛的应用。但是，随着数据点维度值不断增加，目前存在的索引方法效率也在不断下降，有的索引方法甚至比线性搜索方法效率还低。为了解决最近邻搜索面临的高维度问题，近似近邻方法得到的索引结果和精确查询的结果近似相等，而且降低了高维度的计算开销，所以研究人员转向了近似近邻 KNN 查询问题。对于给定的查询点 q ，返回数据集中 ? ?Dist q, p ?cr 距离范围内的 Top ?K 个数据点。其中，数据点 p 与查询点q 之间的真实距离为r ，c为距离近似比例，即距离cr 范围内的数据点都是查询点的候选数据对象，然后计算查询点与候选对象的真实距离，最终返回前 K 个数据点作为最终的查询结果。
6.1工作总结
相似性搜索在信息检索等领域有着广泛的应用。但是，随着数据点维度值不断增加，目前存在的索引方法效率也在不断下降，有的索引方法甚至比线性搜索方法效率还低。为了解决最近邻搜索面临的高维度问题，近似近邻方法得到的索引结果和精确查询的结果近似相等，而且降低了高维度的计算开销，所以研究人员转向了近似近邻 KNN 查询问题。对于给定的查询点 q ，返回数据集中 ? ?Dist q, p ?cr 距离范围内的 Top ?K 个数据点。其中，数据点 p 与查询点q 之间的真实距离为r ，c为距离近似比例，即距离cr 范围内的数据点都是查询点的候选数据对象，然后计算查询点与候选对象的真实距离，最终返回前 K 个数据点作为最终的查询结果。
针对相似性搜索问题，已经提出了许多搜索算法以实现有效的相似性搜索。局部敏感哈希算法（Locality Sensitive Hashing，LSH）及其变体是解决高维数据点近似近邻搜索问题的著名且行之有效的算法。该算法将高维数据点通过哈希函数映射低维的空间，然后将复杂度高的高维空间距离计算转化为复杂度低的低维空间距离计算问题。LSH 能够保证将相似的数据点以高概率的方式映射到相同的哈希桶中，而不相似的数据点以高概率的方式映射到不同的哈希桶中。此外，现有的大多数基于 LSH 的相似性搜索方案被设计为集中式索引，换句话说，是单机方法。但是，面对实际应用中出现了很多大规模的数据集，数据点通常分布在网络不同的位置中，而且传统的集中式相似性索引方案由于存储空间和节点负载不平衡的瓶颈而变得不切实际，这降低了查询系统的整体性能。因此，必须将基于 LSH 的索引方案扩展到分布式数据处理环境。由于分布式的 P2P 网络具有很好的扩展性、鲁棒性强和负载均衡等优点被广泛地应用在各种领域。
参考文献（略）
参考文献（略）