从课程的幻灯片中，我发现：
给定r^d中的一个集合p和一个查询点q，它的nn是p中的点p_0，其中：
dist(p_0, q) <= dist(p, q), for every p in P.
同样，当逼近因子1＞ε＞0时，ε-NN为P0 0，即：
dist(p_0, q) <= (1+ε) * dist(p, q), for every p in P.
（我想知道为什么ε不能达到1）。
我们建立KD树，然后搜索NN，使用以下算法：
就我的思想和测试而言，这是正确的。
我如何修改上述算法，以便执行近似最近邻搜索（ANN）？
我的想法是将当前的最佳值（在叶中的更新部分）乘以ε，剩下的算法保持原样不过，我不确定这是否正确。有人能解释吗？
我理解搜索nn的工作原理。
注意，我在计算机科学网站上，但是什么也没有！
最佳答案
唯一需要修改的是用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+ε)点是否可以满足d(p, q) < d(p_0, q)/(1+ε),
相当于
(1+ε) d(p, q) < d(p_0, q),
这是违反近似最近邻保证的证人。
关于algorithm - 修改此算法以用于最近邻居搜索(NNS)以执行近似NNS，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25790144/