最近邻搜索的学习空间划分
利用深度神经网络 (LLSH) 代替传统的局部敏感哈希函数族,该方法能够高效灵活地将高维数据映射到低维空间,并在同时减少时间和内存消耗、保证查询准确性方面展示了可行性,为开发人员设计和配置数据组织提供了新思路,以提高信息搜索性能。通过在不同类型数据集上进行广泛实验,验证了该方法在查询准确性、时间消耗和内存使用方面的优越性。
Oct, 2023
提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题,并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法(LSH)
Dec, 2015
研究的主题是在多维单位盒子上基于样本的学习条件分布,采用聚类方法,在特征空间中的变化查询点附近聚类数据来创建目标空间的经验度量。聚类方案包括基于固定半径球和最近邻的方法,通过收敛速率的上界确定最佳的半径和邻居数量。通过在实践中进行经验分析,我们的建议是将最近邻方法结合到神经网络训练中,因为它在实践中的性能更好。训练过程利用随机二进制空间划分进行近似最近邻搜索以提高效率。另外,我们使用 Sinkhorn 算法和稀疏强制传输计划。经验研究结果表明,通过适当设计结构,神经网络能够在局部适应适当的 Lipschitz 连续性水平。用于可复现性的代码可在 https://github.com/zcheng-a/LCD_kNN 找到。
Jun, 2024
本文提出了一种基于数据的哈希方案,用于解决近似最近邻问题,对于 $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
本研究综述了基于哈希技术的 ANN 搜索的发展历程和应用,重点介绍了基于数据驱动学习方法和深度学习模型的哈希应用技术,分析了优缺点,并探讨了未来的研究趋势。
Sep, 2015
本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义,并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中;通过 BBD 树等数据结构,可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时,此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{ ho})$ 的查询时间,并可直接解决 approximate nearest neighbor problem 问题,具有比基于 BBD 树的方法更好的查询时间指数。
Dec, 2014
我们提出了 LISSNAS,一种自动算法,它将一个大空间缩小为一个多样化的小搜索空间,具有 SOTA 的搜索性能。我们展示了我们的方法在不同大小和数据集范围的搜索空间上的效果,并在两个不同的搜索空间中实现了最佳的 Top-1 准确率。在移动约束下,我们的方法在 ImageNet 上实现了 SOTA 的 Top-1 准确率为 77.6%,具有最佳的 Kendal-Tau、架构多样性和搜索空间大小。
Jul, 2023
提出了一个新的数据结构用于解决欧几里得空间中近似最近邻问题,其查询时间和空间复杂度分别为 O (n^ρ + dlogn) 和 O (n^(1+ρ)+dlogn),这是对先前算法性能的改进,同时也是第一个突破已有局部敏感哈希下界的数据结构。并可通过标准归约获取解决海明空间和 l1 范数的数据结构。
Jun, 2013