0

私は mysql テーブルを持っています。互いに 1 km 以内にいるすべてのユーザーを見つける必要があります。テーブル:

Geo
----------
id(int)
location(geometry)  with spatial index
username(string)

解決できます：

  1. ユーザー i ... n ごとに繰り返す
  2. インデックスを使用して、特定のポリゴン内のすべてのユーザーを選択するごとに
  3. お互いにメッセージを送る

複雑さは〜O（n）以上（インデックスに依存）になりますが、パフォーマンスが向上する他のソリューションはありますか？

4

2 に答える 2

1

データは 2D であり、半径がわかっているので、データのグリッド インデックスを作成できます。次に、各セルは隣接する各セルにのみメッセージを送信します。

セル割り当ての計算は O(n) です。したがって、これにより、このタスクが に低下するはずです。セルの最大占有率はn * O(m * m)いつmですか。

ここで何かを保証するのは難しいことに注意してください。すべてのオブジェクトが半径 1 km 以内にある場合、インデックスは役に立ちません。誰もが他の人に送信する必要があります.osは二次になります.

于 2013-01-01T16:38:21.963 に答える
0

Mysql は空間インデックスにR-Treeを使用するため、インデックスがメモリに収まる限り、O(n) よりも優れたパフォーマンスが得られるはずです。

于 2012-12-08T22:00:15.950 に答える