Dec, 2014
使用松弛度的随机嵌入和高维近似最近邻
Randomized embeddings with slack, and high-dimensional Approximate Nearest Neighbor
Evangelos Anagnostopoulos, Ioannis Z. Emiris, Ioannis Psarros
TL;DR本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义，并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中；通过 BBD 树等数据结构，可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时，此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{
ho})$ 的查询时间，并可直接解决 approximate nearest neighbor problem 问题，具有比基于 BBD 树的方法更好的查询时间指数。