超越局部敏感哈希

Jun, 2013

Beyond Locality-Sensitive Hashing

Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya Razenshteyn

TL;DR提出了一个新的数据结构用于解决欧几里得空间中近似最近邻问题，其查询时间和空间复杂度分别为 O (n^ρ + dlogn) 和 O (n^(1+ρ)+dlogn)，这是对先前算法性能的改进，同时也是第一个突破已有局部敏感哈希下界的数据结构。并可通过标准归约获取解决海明空间和 l1 范数的数据结构。

Abstract

We present a new data structure for the c-approximate near neighbor problem (ANN) in the euclidean space. For n points in R^d, our algorit

data structure approximate near neighbor problem euclidean space locality-sensitive hashing hamming space

发现论文，激发创造

逼近近邻最优数据相关哈希

本文提出了一种基于数据的哈希方案，用于解决近似最近邻问题，对于 $n$ 个 $d$ 维数据集，我们的数据结构实现了查询时间 $O (d n^{ ho+o (1)})$ 和空间复杂度 $O (n^{1+ ho+o (1)}+dn)$，其中 $ ho= frac {1}{2c^2-1}$，而在 Hamming 空间中，我们获得了指数 $ ho= frac {1}{2c-1}$。此外，我们的结果比所有逼近因子 $c>1$ 的最佳 LSH 数据结构 [IM98, AI06] 更优。

Jan, 2015

基于哈希的近似最近邻时间空间权衡的最优解

该研究论文介绍了时空权衡的上下界，并提出了第一种子线性查询时间和近似线性空间数据结构，可用于每个逼近因子 c>1 的近邻搜索问题，并通过建立一些类推到当地可解码代码的联系来表明两种探针的无条件单元格探针下限。

Aug, 2016

使用松弛度的随机嵌入和高维近似最近邻

本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义，并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中；通过 BBD 树等数据结构，可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时，此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{ ho})$ 的查询时间，并可直接解决 approximate nearest neighbor problem 问题，具有比基于 BBD 树的方法更好的查询时间指数。

Dec, 2014

基于熵的高维最近邻搜索

本文研究在高维空间中，特别是欧几里德空间中找到查询点的近似最近邻的问题，提出了一种用于解决问题的新方法，并分析了其效果，同时改进了局部保持哈希函数以提高最近邻检索效率。

Oct, 2005

有限空间中的近似最近邻

研究了最近邻搜索的问题，提出了一种占用空间小且准确度高的数据结构，能够快速地估算出给定数据点和查询点之间的距离。同时也解决了问题的空间复杂度限制与维数的关系。

Jun, 2018

一般对称范数的近似最近邻

每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度 “top-k” 范数的迭代乘积的低扭曲嵌入。同时，我们证明这些方法无法推广到一般范数。

Nov, 2016

数据相关局部敏感哈希的紧密下界

证明了不同于传统的局部敏感哈希，数据依赖性哈希在设计高效的近似最近邻搜索算法时明显优越，我们证明了 $ ho$ 的下界，要求哈希函数具有简洁性质。