高维近似最近邻搜索
本文研究在高维空间中,特别是欧几里德空间中找到查询点的近似最近邻的问题,提出了一种用于解决问题的新方法,并分析了其效果,同时改进了局部保持哈希函数以提高最近邻检索效率。
Oct, 2005
本文详细评估了 16 种不同算法在 20 个不同数据集、多个评估指标和不同查询工作负载下的性能表现,并提出了一种新的方法以提高查询效率和召回率。
Oct, 2016
本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义,并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中;通过 BBD 树等数据结构,可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时,此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{ ho})$ 的查询时间,并可直接解决 approximate nearest neighbor problem 问题,具有比基于 BBD 树的方法更好的查询时间指数。
Dec, 2014
本文系统综述了最近邻搜索问题中的哈希学习算法,将其按照不同的相似性保存方式进行分类,并分别阐述其性能评估和效益分析,最终指出量化算法在搜索精度、搜索时间、空间花费等方面都表现优异,并介绍了一些新兴话题。
Jun, 2016
本文提出了一种基于数据的哈希方案,用于解决近似最近邻问题,对于 $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
每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度 “top-k” 范数的迭代乘积的低扭曲嵌入。同时,我们证明这些方法无法推广到一般范数。
Nov, 2016
我们定义和研究了 $ extit {c - 近似窗口搜索}$ 的问题,即在数据集中每个点具有数字标签,并且目标是在任意标签范围内找到 Queries 的最近邻。我们提出并理论分析了基于模块化树结构的方法,用于将解决传统 c - 近似最近邻问题的索引转换为解决窗口搜索的数据结构。在标准最近邻基准数据集上,对于具有随机标签值、对抗构建嵌入和具有实际时间戳的图像搜索嵌入,我们在相同召回级别上获得高达 75 倍的加速。
Feb, 2024
提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题,并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法(LSH)
Dec, 2015