Spherical Hashing,球哈希

Introduction

在传统的LSH、SSH、PCA-ITQ等哈希算法中,本质都是利用超平面对数据点进行划分,但是在D维空间中,至少需要D+1个超平面才能形成一个封闭、紧凑的区域。而球哈希方法利用超球面(hypersphere)对数据进行划分,在任何维度下,只需要1个超球面便可形成一个封闭的区域。利用球哈希方法,每个区域内样本的最大距离的平均值会更小,说明各个区域的样本是更紧凑的。这样更符合邻近的含义,更适合在进行相似搜索时使用。

Iterative Quantization,ITQ

Abstract

针对大规模的图像检索问题,论文提出了一个高效的ITQ算法。该算法先将中心化后的数据映射到超立方体的顶点上,再通过优化过程寻找一个旋转矩阵,使得数据点经过旋转后,与超立方体的顶点数据具有最小的量化误差。ITQ算法涉及到了multi-class spectral clustering(不懂)以及Orthogonal Procrustes problem,且可以通过PCA(无监督)或CCA(监督)的方法事先对数据进行降维。该方法的实验结果优于大部分start-of-the-art方法。

Locality Sensitive Hashing, LSH

LSH

局部敏感(Locality Senstitive):即空间中距离较近的点映射后发生冲突的概率高,空间中距离较远的点映射后发生冲突的概率低。

局部敏感哈希的基本思想类似于一种空间域转换思想,LSH算法基于一个假设,如果两个文本在原有的数据空间是相似的,那么分别经过哈希函数转换以后的它们也具有很高的相似度;相反,如果它们本身是不相似的,那么经过转换后它们应仍不具有相似性。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×