問題の説明: 次の問題があります。
3D 空間には 10 億を超えるポイントがあります。目標は、与えられた距離 R 内に最大数の近傍点を持つ上位 N 個の点を見つけることです。別の条件は、これらの上位 N 個の点の任意の 2 点間の距離が R よりも大きくなければならないということです。これらの点の分布は均一ではありません。空間の特定の領域に多くの点が含まれることは非常に一般的です。
目標: 多くのプロセッサに適切にスケーリングでき、メモリ要件が小さいアルゴリズムを見つけること。
考察: 通常の空間分解は、不均一な分布のため、この種の問題には十分ではありません。ポイントの数を均等に分割する不規則な空間分割は、問題を解決するのに役立ちます。誰かがこの問題を解決する方法に光を当てることができれば、本当に感謝しています。
Octreeを使用します。巨大なデータ セットに非常によくスケーリングする限定された値ドメインを持つ 3D データの場合。
局所性に敏感なハッシングなどの前述の方法の多くは、賢明に分割することができなくなるはるかに高い次元向けに設計された近似バージョンです。
各レベルで 8 つのビン (d=3 の場合は 2^d) に分割すると、非常にうまく機能します。また、セル内のポイントが少なすぎる場合は停止し、要件に非常によく適合するポイントが多数ある場合は、より深いツリーを構築できます。
詳細については、ウィキペディアを参照してください。
https://en.wikipedia.org/wiki/Octree
または、R ツリーの構築を試みることもできます。しかし、R ツリーはバランスを取ろうとするため、最も密度の高い領域を見つけるのが難しくなります。あなたの特定のタスクでは、オクトリーのこの欠点が実際に役に立ちます! R ツリーは、各ポイントがほぼ同時に検出されるように、ツリーの深さをすべての場所で等しく保つことに多大な労力を費やします。ただし、オクツリーの最長のパスにある密集した領域にのみ関心があり、実際のポイントをまだ確認する必要はありません。
明確な答えはありませんが、解決策をもたらす可能性のあるアプローチについて提案があります。
locality-sensitive hashingを調査する価値があると思います。ポイントを均等に分割してから、この種の LSH を各セットに適用することは、容易に並列化できるはずです。バケット サイズが で定義されるようにハッシュ アルゴリズムを設計した場合、バケットRに分割されたポイントの特定のセットについて、基準を満たすポイントが最大のバケットに存在する可能性が高くなります。
これをローカルで実行すると、おそらく、ある種の map-reduce スタイルの戦略を適用して、LSH アルゴリズムのさまざまな並列実行からの空間バケットを段階的に結合できます。バケット全体を割引することで、問題のスペースを減らします。明らかに、異なるバケットにまたがるエッジケースに注意する必要がありますが、マージの各段階で、この効果を取り除くように異なるバケットサイズ/オフセットを適用できると思います (たとえば、空間的に同等のバケットのマージも実行します)。隣接するバケットとして）。この方法を使用すると、メモリ要件を小さく保つことができると思います (つまり、任意の時点でポイント自体よりも多くを保存する必要はなく、常に小さな (っぽい) サブセットで操作している場合)。
ある種のヒューリスティックを探しているなら、この結果はすぐに「良い」解決策に似たものをもたらすと思います。つまり、基準を満たすかどうかを確認できるいくつかの可能性のあるポイントが得られます。正確な答えを探している場合は、並列バケットのマージを開始するときに、他の方法を適用して検索スペースをトリミングする必要があります。
私が持っていた別の考えは、これはメトリックk -centerを見つけることに関連している可能性があるということでした. まったく同じ問題ではないことは間違いありませんが、解決に使用されるいくつかの方法がこの場合に適用できる可能性があります。問題は、距離メトリックの計算が可能なメトリック空間があることを前提としていることです。ただし、あなたの場合、10 億のポイントが存在するため、あらゆる種類のグローバルトラバーサル (距離の並べ替えなど) を実行することが望ましくなく、困難になります。ポイント間）。私が言ったように、単なる考えであり、おそらくさらなるインスピレーションの源です.
解決策のいくつかの可能な部分を次に示します。各段階にはさまざまな選択肢があり、Ncluster、データの変化の速さ、および手段で何をしたいかによって異なります。
3 ステップ: 量子化、ボックス化、K-means。
1) 量子化: X、Y、Z の 2^8 パーセンタイルを別々に取得することにより、入力 XYZ 座標をそれぞれ 8 ビットに減らします。これにより、詳細をあまり失うことなく、フロー全体が高速化されます。すべての 1G ポイント、またはランダムな 1M だけを並べ替えて、2^(30- 8) 各範囲のポイント。float X -> 8 ビット x をマッピングするには、展開されたバイナリ検索が高速です — Bentley、Pearls p. 95。
追加: Kd ツリー は、任意のポイント クラウドを異なるサイズのボックスに分割し、それぞれが ~ Leafsize のポイントを持ちます。上記のように XYZ を分割するよりもはるかに優れています。しかし、最初の16Mボックスのみを分割し、ポイントではなくカウントのみを保持するには、独自のKdツリーコードをロールバックする必要があります。
2) ボックス: 各 3d ボックス [xj .. xj+1, yj .. yj+1, zj .. zj+1] 内の点の数を数えます。平均的なボックスには 2^(30-3*8) ポイントがあります。分布は、データがどれだけ塊になっているかによって異なります。いくつかのボックスが大きすぎたり、ポイントが多すぎたりする場合は、a) それらを 8 つに分割し、b) 各ボックス内のポイントの中心を追跡し、それ以外の場合はボックスの中間点のみを取得します。
3) 2^(3*8) ボックスの中心でのK-means クラスタリング。(Google パラレル "k means" -> 121k ヒット。) これは、K aka Ncluster に強く依存し、半径 R にも依存します。大まかなアプローチは 、27*Ncluster ボックスのヒープを最も多くのポイントで成長させてから、半径の制約を受ける最大のもの。(最小スパニング ツリーから始めて 、K-1 個の最長リンクを削除して K 個のクラスターを取得するのが好きです。) 色の量子化も参照してください。
Nbit、ここでは 8 を最初からパラメーターにします。
あなたの Ncluster は何ですか?
追加: ポイントが時間内に移動している場合は、 SOのcollision-detection-of- huge-number-of-circlesを参照してください。
ただのアイデア。距離 < R の場合、指定されたポイントとポイント間のエッジを持つグラフを作成します。
この種のグラフの作成は、空間分解に似ています。あなたの質問は、グラフ内のローカル検索で回答できます。1 つ目は最大次数の頂点、2 つ目は最大次数の頂点の最大の未接続セットの検出です。
グラフの作成と検索が並行できると思います。この方法では、大量のメモリが必要になる場合があります。ドメインを分割し、より小さいボリュームのグラフを操作すると、必要なメモリを減らすことができます。