通过张量化的随机投影来改进 LSH
内容提要
局部敏感哈希（LSH）研究涵盖多个方向：FastLSH通过随机抽样与投影将复杂度从O(n)降至O(m)；密度敏感哈希利用数据几何结构提升高维搜索性能；此外还有分布式分层哈希、角距离LSH族及多探针版本、自动故障分组DeepLSH、设备端隐私个性化框架、双线性随机投影、深度神经网络LLSH，以及核化LSH的重新解释，后者在图像检索中召回率至少提升12%。
延伸解读
LSH 的多样化演进
文章梳理了局部敏感哈希（LSH）的多个研究方向，包括 FastLSH、密度敏感哈希、分布式分层哈希、角距离 LSH 族、DeepLSH、设备端隐私个性化框架、双线性随机投影、LLSH 以及核化 LSH 的重新解释。这些工作分别从效率、数据几何、网络传输、理论最优性、深度学习融合、隐私保护等角度对经典 LSH 进行了扩展，显示出 LSH 研究已从单一算法发展为多维度技术体系。
效率与理论的双重突破
FastLSH 通过随机抽样与投影将时间复杂度从 O(n) 降至 O(m)，并保持可证明的 LSH 属性；角距离 LSH 族则证明了渐进最优运行时间指数的近邻搜索算法，并提供了多探针版本。这些进展表明，LSH 在降低计算复杂度的同时，也在理论层面获得了更优的性能保证，为实际应用提供了更高效的选择。
深度学习与 LSH 的融合
DeepLSH 利用 Siamese DNN 架构和原始损失函数逼近 Jaccard 和 Cosine 度量的局部敏感性，用于自动故障分组；LLSH 则用深度神经网络替代传统哈希函数族，将高维数据映射到低维空间，在减少时间和内存消耗的同时保证查询准确性。这些方法展示了深度学习在提升 LSH 表达能力和适应性方面的潜力。
核化 LSH 的重新解释与性能提升
文章提出对核化局部敏感哈希（KLSH）的重新解释，在投影空间中审视算法步骤，消除了现有动机中的问题，获得了首个正式检索性能界限，并利用改进技术提升经验性能。在大规模基准图像检索数据集上，该分析至少提高 12% 的召回率，有时显著优于标准 KLSH，为图像检索等任务提供了更有效的方案。
Q&A
FastLSH 算法是如何降低局部敏感哈希的时间复杂度的？
FastLSH 通过随机抽样和随机投影的组合，将 LSH 计算的时间复杂度从 O(n) 降低到 O(m)（其中 m < n），并具有可证明的 LSH 属性。
密度敏感哈希（DSH）与经典 LSH 相比有什么优势？
DSH 是 LSH 的扩展，它利用数据的几何结构避免了纯随机投影的限制，从而在大规模高维数据搜索中取得更好的性能。
DeepLSH 是用来解决什么问题的？
DeepLSH 用于解决软件开发过程中自动故障分组的问题，它采用 Siamese DNN 架构和原始损失函数来逼近 Jaccard 和 Cosine 度量的局部敏感性特性。
LLSH 方法相比传统 LSH 有什么改进？
LLSH 利用深度神经网络代替传统的局部敏感哈希函数族，能够高效灵活地将高维数据映射到低维空间，在减少时间和内存消耗的同时保证查询准确性。
核化局部敏感哈希（KLSH）的重新解释方法带来了哪些提升？
该重新解释方法在投影空间中查看 KLSH 算法步骤，消除了现有动机中的问题，获得了首个正式检索性能界限，并利用改进的技术提高了经验性能，在大规模基准图像检索数据集上至少提高 12% 的召回率。
设备端隐私个性化 LSH 框架有什么特点？
该框架使用新的哈希函数族，是第一个在设备上具有私密性、个性化和内存效率高的局部敏感哈希框架，能够与其他 LSH 框架相竞争，并用于训练大规模推荐网络。
