近似最近傍

最近傍問題は次のようになります。n点の集合P = (PI, . . . ,p,)があるメトリック空間Xにおいて、クエリポイントq E Xに最も近いP内の点を効率的に見つけるためにPを前処理します。我々は、d次元ユークリッド空間における特に興味深い場合、すなわちX = WdのZpノルムの下で集中します。数十年の努力にもかかわらず、現在の解は満足のいくものからほど遠いです。実際、大きなdに対して、理論的にも実践的にも、クエリポイントを各データポイントと比較する単純なアルゴリズムに対してほとんど改善が見られません。最近、近似最近傍問題への関心が高まっています。これは、クエリqのc-近似最近傍である点p E Pを見つけることであり、(a) すべてのp' E Pに対してd(p, q) 1); および(b) クエリ時間がlog-nおよびdに対して多項式であり、前処理コストが穏やかに指数的であること* O(n) x 0(1/~)~です。さらに、ランダム投影に関する古典的な幾何学的補題を適用することで（我々はより簡単な証明を提供します）、前処理が多項式で、クエリ時間がdおよびlog nに対して多項式であることが知られている最初のアルゴリズムを得ます。残念ながら、Eが小さい場合、後者は理論的な結果に過ぎず、指数はl/eに依存します。実験結果は、我々のアルゴリズムが情報検索、パターン認識、動的最近対、迅速なクラスタリングアルゴリズムに応用されることを示しています。