java - 地理的半径に基づいてツイートをクラスタリングするアルゴリズム

Question

(10 メートル) のような指定された地理半径に基づいてツイートをクラスター化したい。たとえば、半径 10 メートルを指定した場合、10 メートル以内にあるすべてのツイートを 1 つのクラスターにする必要があります。

単純なアルゴリズムは、各ツイートと他のツイート間の距離を計算することですが、計算コストが非常に高くなります。これを行うためのより良いアルゴリズムはありますか?

Answer 1

問題が距離の計算のみにある場合:

1. 覚えておいてください: 比較のためだけに距離が必要な場合は、決して距離を数えるべきではありません。代わりにそれらの正方形を使用してください。

   比較しない:

   sqrt((x1-x2)^2+(y1-y2)^2) 対 10

   代わりに比較する

   (x1-x2)^2+(y1-y2)^2 対 100

   時間が大幅に短縮されます。

2. 距離の 2 乗を比較する前に座標を単純に比較すると、もう 1 つの改善点が得られます。abs(x1-x2)>1 の場合、そのペアはもう必要ありません。(MrSmith さんが話しているマンハッタン距離です)

3. ポイントをどのように処理するかはわかりませんが、それらのセットが安定している場合は、それらの 2 つの配列を作成し、それぞれの配列を座標の 1 つに従って並べることができます。その後、両方の配列でソースに近いこれらのポイントのみをチェックする必要があります。