〜10.000点の座標リスト（latitute、longits）と〜100万点の同じ種類の座標リストBがあります。他の点から最も近い点を効率的に見つける
私は、リストBの各要素のリストAにおける最も近い点を見つけたい
私がすでにやっていることは二つのリストの直積を作成し、半正矢を使用してすべての組み合わせの距離を見つけることです式。
そしてIは、総組み合わせは100億以上であるので、距離を計算するのにかかる時間が長すぎるリストBに
の各点の最小距離を有する、リストAのポイントを得ます。
リストBのすべてのポイントがリストAのポイントと一致するようにする方法はありますか？
すでにクロス製品を作成し、すべてのhaversine距離を計算した場合は、すでに大部分の作業を完了しているので、新しいセットAとBがある場合の対処方法について質問します
AIの最も近い点を繰り返し見つけると、Aの点を含む何らかの種類のツリー構造が構築され、樹木の各ノードに情報が格納され、すべての子孫を囲む境界ボックスまたは同等のものになります。次に、Aに最も近い点を見つけようとするときに、Aを含むツリーを再帰的に検索し、ノードに到達したときに再帰呼び出しから戻り、そこに格納されている情報から、その子孫のすべてがターゲット点から遠いこれまでの最も近いマッチよりも。
バウンディングボックスの情報は正確である必要がありますが、ツリーがばかばかであれば検索が遅くなりますが、正しい答えを見つけることができなくなりません。これは特に、ツリーを構築するとき180W = 180Eでラウンドラウンドするという不都合な習慣を無視できることを意味します。 lat-longは長方形のグリッドでkdツリーを構築し、緯度と経度を組み合わせてビットインターリーブし、結果に1次元の検索ツリーを作成することができます。https://en.wikipedia.org/wiki/Geohashを計算して検索ツリーを構築できますまたは、あなたはhaversineをたくさん計算してhttps://en.wikipedia.org/wiki/Cover_treeを構築することができます。これらのすべてがうまくいくはずです。これはあなたのデータと利用可能なライブラリによって異なる場合があります。
spatstatパッケージのnncross関数を使用して、2つの異なるデータセットからの距離を見つけることができます。この関数を使用すると、時間が大幅に短縮されます。 https://www.rdocumentation.org/packages/spatstat/versions/1.53-2/topics/nncross
私は質問に詳細を追加することを検討します。予想される最小距離はどれくらいですか？覆われた面積はどれくらいですか？球のどの部分？ 'A'サイズは固定されていますか？正確なソリューションが必要ですか？データに応じて動作するかどうかは、より小さなリストでkdtreeを構築し、それを使ってRDD上にマッピングすることです。 – zero323