1

地球上の100万の（ゆっくりと）移動するポイントのリストがあります（緯度と経度として保存されています）。ときどき、各ポイントは 100 個の最も近い他のポイントのリストを要求します (それが役立つ場合は、構成可能な最大範囲を使用して)。

残念ながら、SELECT * SORT BY compute_geodetic_distance() LIMIT 100各ポイントで何度も何度も実行するには遅すぎます。だから私の質問：これを効率的に処理するにはどうすればよいですか？より良いアルゴリズム/データ構造/...これで知られていますか? または、これが唯一の方法であり、サーバーの負荷を分散することを検討する必要がありますか?

（注：これはAndroidアプリ用であり、ポイントはユーザーであるため、Android固有のソリューションが不足している場合は、遠慮なく言ってください！）

4

4 に答える 4

1

あなたの仕事のために、地理空間データベースが発明されました。
Oracle Spatial (有料) と PostGres (無料) があります。
これらのデータベースは、何百万ものポイントを地理的なインデックスであるクワッド ツリー (Oracle) に保存します。このようなクエリにはほとんど時間がかかりません。

私のような一部の人々は、データベースを離れて自分で四分木を構築することを好みます。

検索と挿入の操作は簡単に実装できます。更新/削除はより複雑になる可能性があります。

四分木を使用すると、そのような最も近い 100 ポイントを 1 秒以内に数百または数千実行できます。

于 2013-06-12T18:13:55.973 に答える
0

アーキテクチャ的には、各「ポイント」が特定の量を超えて変化したときに、その場所をサーバーに電話するように手配します。サーバー上では、移動したポイントと他の各ポイントの間の距離を計算し、必要に応じて他のポイントごとに 100 個の最も近いポイントのリストを更新するという面倒な作業を行うことができます。次に、変更が発生したときに、ポイントに最も近い 100 リストに変更をプッシュできます (App Engine を使用している場合は簡単です。Android のプッシュがサポートされています)。

これにより、関連する作業量が最小限に抑えられます。

  • ポイントが十分に移動した場合にのみ、場所の変更を報告する
  • レポートを受信したときのみ距離を再計算する
  • ポイントの最も近い 100 のリストを毎回再構築するのではなく、一度リストを作成してから、移動したポイントが他のすべてのポイントのリストに追加または削除されるかどうかを調べます。
  • 帯域幅を維持するために、上位 100 リストへの変更点のみを通知します。

これを非常に効率的にするために使用できるアルゴリズムがあり、問題にはフォーク/ジョインの感覚もあり、問題に馬力を投入できます。

于 2013-06-12T16:27:21.230 に答える