发现数据结构：最近邻搜索及其他
本研究综述了基于哈希技术的ANN搜索的发展历程和应用，重点介绍了基于数据驱动学习方法和深度学习模型的哈希应用技术，分析了优缺点，并探讨了未来的研究趋势。
Sep, 2015
提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题，并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法（LSH）
Dec, 2015
本研究提出一种新的框架用于构建空间划分，将问题转化为平衡图划分和监督分类，并结合KaHIP图分区器和神经网络，实现了一种新的分区过程称为神经局部敏感哈希（Neural LSH），实验证明Neural LSH的分区在标准最近邻搜索（NNS）基准测试中，始终优于基于量化和树的方法，以及经典的数据无关LSH。
Jan, 2019
本条研究提出了史上首个可查询到数据集中最近邻居的亚线性内存草图，并利用局部敏感哈希（LSH）估计器、在线核密度估计和压缩感知相结合来实现稳定查询的子线性内存性能，以取得内存-精度权衡的理论效果。
Feb, 2019
Falconn++是一种基于哈希的近似最近邻搜索算法，它利用本地敏感过滤技术过滤掉潜在的远点，实现了比其他哈希方案更高质量的候选结果，与在许多真实数据集上表现优异的HNSW相比具有更高的召回速度折衷。
Jun, 2022
在机器学习和经典数据结构的交叉领域中，这项研究关注了学习数据结构，这是一个具有重要方法论意义和高实用性影响的新领域。我们提出了一种新的思路，通过对任何排序集合字典进行学习，例如平衡二叉搜索树或其他非排序布局的二分搜索，从而在时间性能上取得了令人印象深刻的提升。
Sep, 2023
图形化相似最近邻搜索算法的最坏情况性能研究，以HNSW、NSG和DiskANN为例，发现其实际查询时间与实例大小成线性关系，并证明其具有常数近似比和多对数查询时间的边界维数据集。
Oct, 2023
通过将机器学习建议整合到跳跃表的设计中，我们改进了传统数据结构设计，并构建了一种能够在几乎两倍内提供最优预期搜索时间的学习增强型跳跃表，即使预估的搜索查询存在误差，该方法依然能够是唯一最优的，而且如果搜索查询符合普遍存在的齐夫分布，那么我们的跳跃表的预期搜索时间只是常数，与项的总数量无关，而传统跳跃表的预期搜索时间则是对数时间。同时，通过实证研究，我们证明了我们的数据结构在合成和真实数据集上均优于传统跳跃表。
Feb, 2024
我们提出了一种新的“双度量”框架，用于设计最近邻数据结构。我们的框架基于两个不相似性函数：一个准确但计算代价高的基准度量，和一个廉价但不太准确的代理度量。我们在理论和实践中展示了如何仅使用代理度量构建数据结构，使查询过程达到基准度量的准确性，同时只使用有限次对两个度量的调用。我们的理论结果在两个最流行的最近邻搜索算法（DiskANN和Cover Tree）中实例化了该框架。对于任意一个这两个算法，只要用于构建数据结构的代理度量相对于基准度量有界因子的近似，我们的数据结构都能在基准度量方面获得任意好的近似保证。在实证方面，我们将该框架应用于具有计算代价差异的两个机器学习模型评估的文本检索问题。我们观察到，在MTEB基准测试中，对于几乎所有的数据集，我们的方法能够在准确度和效率之间获得相比其他方法（如重新排序）更好的平衡。
Jun, 2024