ANN検索は、高次元表現を持つ大規模データベースでNN検索の精度を上回ることはできますか？

Question

ANN検索は、効率の面でNN検索より優れていることが知られており、一部の手法では、コンパクト表現からストレージスペースが削減されます。しかし効果の点ではどうなるでしょうか？徹底的な検索で最も近いネイバーを見つけずに同じパフォーマンスを達成することは可能ですか？

Answer 1

私はip2locationデータベースでバイナリ検索とアン検索を試みました。速度は同じですが、多くの最適化があります。ソースコードはhttps://ip2locationphp.codeplex.com/にあります。

Answer 2

有効性とは正確度（正確な最近隣を見つける）、次になしを意味します。 NN検索では常に正確なNNが検索されますが、ANN検索ではNN検索の結果との結びつきである正確なNNが検索されます。

しかし、高次元空間において、次元の呪いが潜んおよび2Dおよび3Dのための通常のデータ構造及びアルゴリズムは力まかせ探索ほど遅くなる傾向があり、従ってANN探索が移動するための方法でありますあなた（大きい）データが高次元の空間に住んでいるとき。