超球面上の別の点と最も近い点

Question

私は、次元mの超球面上に（約10^4から10^6まで）n（約10^5）点を持っています。

私は「ポイントpを与えられ、nポイントのうち最も近いものをpに」という形式のクエリをたくさん作成します。私は約n件の質問をします。

（超球の事実はまったく役立ちますかどうかわからない。）

これを解決するための簡単な素朴なアルゴリズムは、他のすべてのn個の点にPを比較するために、各クエリのために、です。これをn回実行すると、実行時間がO（n^2 m）になってしまいます。これは計算できないほど大きくなります。

もっと効率的なアルゴリズムがありますか？もし私がO（nm）にそれを得ることができれば、いくつかの対数要因が良いでしょう。

Answer 1

おそらくそうではありません。多くのディメンションを持つと効率的なインデックス作成が非常に難しくなります。そういうわけで、人々は次元の数を扱いやすいものに減らす機会を模索しています。

https://en.wikipedia.org/wiki/Curse_of_dimensionalityおよびhttps://en.wikipedia.org/wiki/Dimensionality_reductionを参照してください。

Answer 2

スペースをハイパーキューブに分割します。これらのセルを平均サイズで1キューブあたり1つのポイントが選択されるように選択します。あなたは、ハイパーセルからそれらに含まれるポイントのセットまでのマップが必要になります。

次にポイントが与えられたら、ハイパーセルの他のポイントを確認します。それが空であれば、隣接するハイパーセルを見てください（ハイパーセルから作られたハイパースフィアの近似ではなく、簡単にハイパーセルのリテラルなハイキューブをお勧めします）。それ以外の点を確認してください。あなたがポイントを得るまで繰り返す。あなたのポイントがランダムに分布していると仮定すると、オッズは高くなりますので、1〜2回の展開で2番目のポイントを見つけることができます。

ポイントを見つけたら、近くのポイントを含む可能性のあるすべてのハイパーセルをチェックします。あなたが見つけたポイントが角にあるかもしれないが、今まで検査したすべてのハイパーセルを含むハイパーキューブの外に、より近い点があるので、これは可能です。