位置敏感哈希Locality-SensitiveHashing 图像检索其基本定义为给定的⼀个包含个图像数据集，每个图像可以⽤⼀个维的特征向量来描述，因此整个图像数据集就映射为维空间的个点，在此维空间中⽤⼀个相似度度量函数来测量两个图像点之间的距离，对于任意给定的查询点，需要设计⼀个数据结构，来快速的返回距离最近(Nearest Neighbor)的图像点(或者Ranking的多个点)。
当较⼩时(10-20)，可采⽤如的结构，但当较⼤时(⼀个Discriminative的图像描述向量通常成百上千甚⾄万维)，其查询时间将随指数级增长，这就是通常所说的维数灾难"the cur of dimensionality", 同时较⼤时，其所需的存储空间也变的intolerable。因此降维和Approximation NN算法通常会⽤到当前的检索系统中，ANN搜索就是对于给定的查询点，若数据集中存在点距其⼩于距离，允许系统返回点，where，则称为搜索。
当前图像检索要求快、准、同时可容易的扩展⾄⼤规模数据web-scale:
Fast：hashing structure，small code， ANN;
Accurate: discriminative feature fingerprint;
Scalable: very little memroy.
由此可见，紧凑的fingerprint和有效的hash结构对整个检索系统⾄关重要,⽬前的图像检索系统中，常采
⽤Hashing技术将⾼维的图像特征编码为低维的特征，在映射后的空间中采⽤⼀定的距离度量进⾏Approximation Nearest Neighbors (ANN)搜索:
定义Hash函数集：， 是原始的 维特征空间， 是经hash函数集 散列后的 维空间，根据哈希函数设计的不同，可将Hashing分为data-independent和data-dependent两⼤类：
(1) data-independent hashing包括：Locality-Sensitive Hashing (LSH), 经Hash函数映射后，仍保留原始空间的距离相似度；
(2) data-dependent hashing包括：spectral hashing, mi-supervid hashing, Restricted Boltzmann Machine (RBM), Boosting SSC等，引⼊机器学习算法，基于数据分布设计Hash函数。
在此主要介绍Locality-Sensitive Hashing，主要是解读相关原始Paper
===============================================LSH====================================================
位置敏感哈希Locality-Sensitive Hashing (LSH)，其基本的思想就是通过哈希函数将输⼊的⾼维特征⽮量散列⾄低维特征空间，并满⾜在原始空间中距离较近的点经过散列之后在低维空间依然距离较近，距离较近的点散列后碰撞的概率要⼤于距离较远的点碰撞的概率。⽤数学语⾔描述即为：
为距离阈值，是距离函数，如欧式距离：
若，则的概率⾄少为()；
若 ，则的概率⾄多为(),；
当时，称为 -nsitive, 也称为(R, c)-NN.
---------------------------------------------------
常⽤的⼏种LSH构建⽅法：
1. Bit sampling for Hamming distance
最简单的Hash函数，仅适⽤于原始特征空间是Binary的Hamming空间，即原始的特征向量每⼀维的取值为{0，1}的特征串，其Hash函数的基本思想就
是随机选取维特征向量中的某⼀维：
2. Random projection
The random projection method of LSH is designed to approximate the cosine distance between vectors.
机器人英文翻译Hash函数设计的基本思想就是定义⼀个随机超平⾯，，可看做分别是超平⾯的斜率和截距(参照⼆维平⾯直线的定义)，超平⾯将整个原始的特征空间划分为两部分(平⾯的两侧)，⽤{0, 1}表⽰，则Hash函数的映射过程为：
是 维的法向单位向量，即，每⼀个不同的即定义⼀个超平⾯(可令=0).
可证明两个特征vector经Hash函数散列后碰撞的概率和其在原始空间的余弦距离成正⽐，即，是vector 的夹⾓，和余弦距离成正⽐.
3. Stable distributions[2]
Hash函数设计的基本思想也是定义⼀个随机超平⾯，不同于2.之处在于Hash函数将维的特征⽮量散列到之间的⼀个整数⽽不是{0, 1}⼆值码，其Hash过程：
是 维向量，每⼀维都是⼀个随机变量，各维之间独⽴同分布，服从⼀个Stable Distribution， 是⼀个间均匀分布的随机变量。
稳态分布的定义：
A distribution over is called p-stable, ifthere exists such that for any real numbers and i.i.d. variable
s with distribution , the random variable has the same distribution as the variable where is a random variable with distribution.
简⽽⾔之就是若随机变量线性组合的分布与随机变量乘⼀个 归⼀化系数服从同⼀分布，则此分布即为稳态分布，对于 ，都存在⼀个稳态分布, 两个常⽤的Stable Distribution：
Cauchy distribution: 1-stable即 稳态，其概率密度函数为:
loo changeGaussian distribution: 2-stable 稳态，概率密度函数为:
由稳态分布的性质，我们可以看出基于稳态分布Hash函数设计的思想：
将 维的向量映射到⼀条直线，将此直线划分为 ⼤⼩等间隔的段，则哈希函数 将向量映射到直线的某⼀段；
中每⼀维 都是⼀个稳态分布的变量，因此是稳态分布变量的线性组合，因此的分布等价于 的分布；
support是什么意思
由此，可得出对于两个原始空间的向量，其映射后的距离为，其分布等价于 的分布， 是原始空间向量之间的距离，只需证明 ，即两个向量经Hash函数映射后碰撞的概率反⽐于两个向量之间的 距离。
令， ，则对于上述两个稳态分布，可得出：
focus
Cauchy distribution:
shmily是什么意思Gaussian distribution:
read怎么读
雅思英语怎么学是正态分布 随机变量的累积分布。
p-Stable Hashing 的具体使⽤：
由于LSH构建Hash函数的过程是独⽴于数据分布的，因此为了提⾼检索的Recall率，常采⽤多个Hash表，通过表之间的冗余互补来弥补Hash
的ineffective，例如构建个Hash表，每个Hash表都可通过⼀个函数产⽣，其包含其个相互独⽴的Hash函数，将 维的原始特征 映射⾄ 维。个表需要个Hash函数(为Hash函数集)，且其相互之间要保持独⽴性。
(1) 构建Hash函数及Hash Table
基于上述构建Hash表的过程，涉及两个参数 和，通常令：
淄博市会计网其中，为总的数据点数， 为中的，其中 通常设为1 (仅是距离的尺度变换)；
系统占⽤的空间复杂度为 ，查询时间复杂度为 ；
monica什么意思当取值为1时，可得出，，其中 即为上述得出的距离or碰撞的概率分布函数，因此是的函数，
是和的函数===》即为和的函数，⼜由于影响系统性能(空间复杂度和时间复杂度)的主要因⼦是，因此需要优化即选取合适的和使其取得极⼩值，约束条件： && 。其中是ANN搜索时的最近邻因⼦，通常是根据实际系统的性能需求确定的，因此优化过程也就退化为对于给定的，选取最优的的问题。
实际实践过程，对于给定的数据集(个数据点)，我们要确定的就是，和：
是'width' of Hash函数，值越⼤，计算Hash值的时间就越多，经Hash散列后的低维空间维度也越⾼，碰撞的概率就会越⼩；
是映射直线分割的线段长度，越⼩，经Hash散列后碰撞的概率就会越⼩；
是Hash表的个数，越⼤，则查询过程需要的时间越多，同时召回率(Recall)会提⾼，⽽由此产⽣的fal positive也会变⾼；
实际使⽤中，通常会按照上述的优化过程选取，和参数，开源软件E2LSH中有具体实现。
(2) 查询过程
对给定的查询向量 ，计算每个Hash表中其对应的Bucket，计算相应Bucket中所有点和的距离, 返回距离⼩于的点。在实际使⽤过程中，由于所有Bucket的点可能⾮常多，通常指选取⼀定数量的点进⾏距离计算并返回，常取First个点(Including duplicates)
开源软件
参考⽂献
sheets
[2] Datar, M.; Immorlica, N., Indyk, P., Mirrokni, V.S. (2004).. Proceedings of the Symposium on Computational Geometry.
