すべてのデバイス (道路上を移動) が 30 秒ごとに座標をサーバーに送信する GPS アプリケーションを開発しました。次に、これらのデバイス間の距離を計算する必要があるため、いずれかのデバイスが別のデバイスの範囲内に入ると、両方のデバイスが通知を受け取ります。
2 つの座標間の距離を計算する方法は知っていますが (Google のおかげです)、実装方法がわかりません。サーバーにデータを同時に送信するデバイスが 100 万台ある場合、サーバーは距離計算を 30 秒ごとに 100 万 * (100 万 - 1) 回実行する必要があります。
実装方法を教えてください。ジョブを実行するために、Hadoop や MySQL データベース プロシージャなどを使用する必要がありますか? 計算はここでは問題ありませんが、これだけのデータの処理と計算は問題です。
QuadTreeと呼ばれるデータ構造があります。四分木でデータ ポイントを更新し続けると、値を比較するデータ セットがはるかに小さくなります。
クライアントがログインして移動し、データポイントを送信すると、クワッド ツリー内の場所が変更されます。QuadTree は、すべてのデータポイントの 2D マップをバケットに分割します。各バケットには、ポイントがある場合とない場合がある 4 つの他のバケットが含まれます。特定のデータ ポイントの X 内にいる全員を見つけようとする場合、そのポイントが含まれるバケット内のすべてのポイントを調べます。次に、そのバケットの「周囲」のバケット内のすべてのポイントを調べます。(8 個あります。NSEW NW SW NE SE。) バケツまでの距離 (したがってバケツ内のすべてのポイント) が最小範囲より大きくなるまで進みます。
現在、ほとんどの人はおそらく非常に遠く離れており、検査を受ける必要はありません。彼らのバケツを見ることはありません。