mapreduce - 空間データの局所性に依存するハッシュ

Question

空間データを多数のバケット (リデューサー タスク) に分割するために、局所性に敏感なハッシング アルゴリズムを見つけたいと考えています。空間データは実際には軌跡であるため、LSH を控えめに説明すると、軌跡は一連の 2d ポイントで表されます。

ありがとう、アダム

Answer 1

ほとんどの場合、QuadTreeが必要です。

「四分木は、2 次元空間を再帰的に 4 つの象限または領域に分割することによって、2 次元空間を分割するために最もよく使用されます。」

実際のポイントを四分木に保存し、四分木内のポイントを参照するインデックスのリストとして軌跡を定義できます。