代码之家 › 专栏 › 技术社区 › gsamaras

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

approximate-nn-searching kdtree nearest-neighbor search algorithm

0

gsamaras · 技术社区 · 10 年前

从一门课程的幻灯片中,我发现:

给定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: enter image description here 就我的想法和测试而言,这是正确的。

为了执行近似最近邻搜索(ANNS),我应该如何修改上述算法?

我的想法是将当前最好的(在叶更新的部分)与算法的其余部分相乘并保持原样。然而,我不确定这是否正确。有人能解释一下吗?

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

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

1 回复 | 直到 7 年前

1

2

David Eisenstat 10 年前

所需的一项修改是替换 current best distance 具有 current best distance/(1+Îµ) 这将修剪不能包含违反新不等式的点的节点。

这项工作的原因是(假设 cut-coor(q) 在左侧)测试

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

正在检查超平面是否分离 left-child 和 right-child 比 当前最佳距离 ,这是 正确的孩子 比查询点更近 q ,作为线段连接 q 还有一点 正确的孩子 通过该超平面。通过替换 d(p_0, q) = current best distance 具有 当前最佳距离/(1+) ,我们正在检查是否有任何问题 p 在右边可以满足

d(p, q) < d(p_0, q)/(1+Îµ),

相当于

(1+Îµ) d(p, q) < d(p_0, q),

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