algorithm - 为最近邻搜索 (NNS) 修改此算法以执行近似 NNS

Question

从类(class)的幻灯片中，我发现了这些:

给定R^D中的集合P，和查询点q，其NN为P中的点p_0，其中:

dist(p_0, q) <= dist(p, q), for every p in P.

类似地，对于近似因子 1 > ε > 0，ε-NN 是 p_0，这样:

dist(p_0, q) <= (1+ε) * dist(p, q), for every p in P.

(不知道为什么ε不能达到1)

我们构建了一个 KD 树，然后我们用这个算法搜索 NN: 就我的想法和测试而言，这是正确的。

我应该如何修改上述算法，以便执行近似最近邻搜索 (ANNS)？

我的想法是将当前最好的(在叶子中的更新部分)乘以 ε 并保持算法的其余部分不变。但是，我不确定这是否正确。谁能解释一下？

PS - 我了解搜索 NN 的工作原理。

注意我 asked在计算机科学网站上，但我一无所获!

Answer 1

需要进行的一项修改是将 current best distance 替换为 current best distance/(1+ε)。这会修剪不能包含违反新不等式的点的节点。

这样做的原因是(假设 cut-coor(q) 在左边)测试

cut-coor(q) + current best distance > node's cut-value

正在检查分隔left-child 和right-child 的超平面是否比current best distance 更近，这是必要的right-child 中的点比查询点 q 中的点更近的条件，作为连接 q 和中的点的线段right-child 通过该超平面。通过将 d(p_0, q) = current best distance 替换为 current best distance/(1+ε)，我们检查是否有任何点 p 右边可以满足

d(p, q) < d(p_0, q)/(1+ε),

相当于

(1+ε) d(p, q) < d(p_0, q),

这是违反近似最近邻保证的见证。