IT·行·思·录

自1998年提出LSH，距今已经10多年了，中间有不少对该算法的改进、挑战、应用、介绍等等。这里根据自己的学习过程，列一个LSH参考文献和相关资源列表：一则是小结学习LSH可以参考的资料，二则是为了避免本人的LSH小结系列文章对大家产生误导。欢迎对该列表进行指正和补充。 LSH原理相关重要论文 1. P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[A]. In STOC ’98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, New York, USA: ACM Press, 1998:604–613. 作者在这篇论文中第一次提出了LSH。 2. Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing[A]. In VLDB [...]

LSH，是Locality Sensitive Hashing的缩写，也翻译为局部敏感哈希，是一种通过设计满足特殊性质即局部敏感的哈希函数，提高相似查询效率的方法。    虽然从正式提出距今不过十余年，由于其局部敏感的特殊性质，以及在高维数据上相当于k-d树等方法的优越性，LSH被广泛地运用于各种检索（包括并不仅限于文本、音频、图片、视频、基因等）领域。      从本科毕业设计时与LSH第一次打交道后，我陆陆续续在不同情况下与LSH打交道，期间其带来的各种事情几乎令我发疯……不过值得庆幸的是与此同时对它的认识越来越深，为了更加深刻地理解LSH，我决定写一系列的博客来介绍自己对LSH的认识和看法。      下面是我初步拟定的一个计划： 入门篇：LSH基本思想（入门性质介绍，为什么会产生LSH即其解决的是哪类问题，LSH发展历程，LSH思想的直观描述） 资料篇：LSH参考文献（小结自己接触LSH时参考的各种资料，以及并附自己对这些文献的一点说明，放在最前面是为了防止我的介绍产生误导） 原理篇：LSH的基本原理（LSH基本思想和原理，以及相对其它方法的优越性，可能涉及部分证明） 实现篇：LSH函数(族)设计（LSH的关键部分，针对不同的场景或距离度量方法设计相应的哈希函数） 应用篇：LSH库和Case Study（列出一些开源或可免费使用的库(以及使用方法)，说明一些LSH的应用场景，不是小结，因为LSH应用方面的论文实在太多，而且还在源源不断地出现，以后还有可能成为一种基础算法） 番外篇：我与LSH纠缠不清的孽缘（对我而言肯定不是一段愉快的经历，但是肯定是最容易写的一篇，介绍我与LSH的一次次接触的感受，也简洁说明我为什么“一定要”写这个LSH系列）     这些内容来自于本人一篇未完成的综述和相关学习笔记。由于自从有写综述到吐血的经历后，我就对写小结产生了深深的恐惧，所以这个系列的博文可能要持续很长的周期。以上6个主题并不一定按列出顺序出现也可能不是正好6篇，不过肯定的是这个系列一定会写完。      非常欢迎对LSH感兴趣的朋友就该系列博文进行讨论和指正其中的各种错误。 注2：由于各种缘由，在未得到本人确认的情况下，LSH系列博文不接受转载。

由于设计LSH哈希函数族的复杂性，可以通过调用已有的实现如E2LSH、LSHKIT进行相关实验，E2LSH库由LSH算法提出者的学生开发。关于该库的详细实现细节和使用可参考作者书写的User Manual和代码，如下是该库使用方法简单说明。 1、安装： 在安装有Linux操作系统的计算机上，解压E2LSH库代码包； 由于E2LSH默认最多输出10个数据，可以通过修改源代码使得E2LSH输出所有查询结果：改变sources/BasicDefinitions.h中第26行MAX_REPORTED_POINTS的数值； 进入在E2LSH目录，执行make编译库文件。 2、E2LSH的调用： 安装E2LSH库后，在E2LSH的bin目录下有完成大部分功能的shell脚本； 通过执行bin/lib下的脚本文件完成相关的查询，调用格式为： 其中各参数为查询距离r、命中概率p、使用LSH哈希的所有点数据文件datafile、用于查询的数据文件queryfile。 该查询会自动调用相关脚本计算LSH哈希函数组参数k，l的最佳选择；由于算法中需要查询所有点的近邻，故datafile和queryfile的内容均为所有数据点。 3、结果的提取： LSH脚本执行后的结果将从输出到标准输出，一个点的输出结果格式为： 即每个数据点对应输出的第三行起为结果（含数据点自身），读取对应序号即可。 文件最后一行为平均查询时间，一个样例如下：   4、相关资料： [1] Alex Andoni. E2LSH User Manual. http://web.mit.edu/andoni/www/LSH/manual.pdf [2] Alex Andoni, Piotr. Indyk, LSH Algorithm and Implementation. http://web.mit.edu/andoni/www/LSH/ [3] Wei Dong, LSHKIT: A C++ Locality Sensitive Hashing Library. http://lshkit.sourceforge.net，2009-9-17. [4] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search [...]