从课程的幻灯片中，我发现了这些：
给定 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-tree，然后我们使用这个算法搜索 NN：
就我的想法和测试而言，这是正确的。
我应该如何修改上述算法，以执行近似最近邻搜索 (ANNS)？
我的想法是将当前最佳值（在叶子中的更新部分）乘以 ε，并保持算法的其余部分不变。但是，我不确定这是否正确。有人可以解释吗？
PS - 我了解搜索 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，这是一个点 inright-child比查询点 更接近的必要条件q，因为连接的线段q和一个点 inright-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),
这是违反近似最近邻保证的见证。