最近邻查找的快速精确检索（FERN）
原文中文，约300字，阅读约需1分钟。发表于：。我们提出了一种受 kd 树启发的新算法，名为快速精确最近邻查找 (FERN)，该算法实现了 O (dlogN) 的查找并在一千万个由 128 维度均匀随机生成的向量上实现了 100% 的召回率。
本文提出了一种新的“低质量”嵌入定义，通过随机投影将问题降低到与目标空间中近似最近邻的k个近似最近邻象限所对应的原像空间的维度成反比的空间中。通过BBD树等数据结构，可以有效检索这k个近似最近邻点。此方法可以获得所需的线性空间和时间复杂度为O(dn^ho)的查询时间，并可直接解决approximate nearest neighbor problem问题，具有比基于BBD树的方法更好的查询时间指数。
