algorithm - Nearest Neighbor Search (NNS) のこのアルゴリズムを変更して、近似 NNS を実行します。

Question

コースのスライドから、次のことがわかりました。

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 の検索の仕組みを理解しています。

Computer Science のサイトで質問したのに、何も得られなかったことに注意してください。

Answer 1

必要な 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-childqqright-childd(p_0, q) = current best distancecurrent best distance/(1+ε)p

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

これはと同等です

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

これは、おおよその最近傍保証の違反の証人です。