最近邻查找的快速精确检索（FERN）

BriefGPT - AI 论文速递 · 2024-05-07T00:00:00Z

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