時空間データ (x、y、z、time) を並べ替えるためにデータ構造を使用したいと考えています。
現在、処理アルゴリズムは、球形 (3d) の空間半径と線形 (1d) の時間半径を指定して、一連の 4D (x,y,z,time) ポイントを検索し、各ポイントをマークし、他のポイントがそれらの半径内にあります。その理由は、処理後、任意の 4D 点に O(1) 時間ですべての隣接点を求めることができるからです。
ただし、空間半径と時間半径の一部の一般的な構成では、アルゴリズムの最初の実行に約 12 時間かかります。信じられないかもしれませんが、これは業界に存在するものと比較して実際に高速です。それにもかかわらず、私は最初の実行をスピードアップしたいので、知りたいです: kdツリーは4D時空間データに適していますか?
最近傍検索や k 最近傍検索の実装を探しているわけではないことに注意してください。
より詳しい情報：
サンプル データセットには 450,000 の 4D ポイントがあります。
一部のデータセットは時間密度が高いため、時間で並べ替えると処理が確実に節約されますが、それでも多くの距離チェックが必要になります。
時間は Excel スタイルの日付で表され、通常は 30,000 ～ 39,000 (概算) の範囲です。空間範囲は高い値の場合も低い値の場合もありますが、各空間座標間の範囲は時間に似ています (例: maxX-minX ~ maxT-minT)。
さらに詳しい情報:
誰かが同様のデータセットを扱った場合に備えて、少し無関係なデータを追加すると思いました。
基本的に、複数のセンサーによって記録および裏付けられた時空間イベントを表すデータを扱っています。エラーが含まれているため、エラーのしきい値を満たすイベントのみが含まれます。
これらのデータセットの期間は、5 ～ 20 年のデータの範囲です。
非常に古いデータ (>8 年) の場合、2 つの理由により、イベントは非常に空間的に高密度であることがよくありました。低誤差で確認。さらにイベントを記録できましたが、エラーが多すぎました
新しいデータ (8 年未満) の場合、逆の理由で、イベントは非常に時間密度が高くなることがよくあります。1) 通常は多くのセンサーが利用可能であり、2) センサーはより長い距離にわたって一定の間隔で配置されています。
その結果、データセットは通常、時間密度が高いだけ、または空間密度が高いだけであるとは言えません (新しいデータのみを含むデータセットの場合を除く)。
結論
明らかに、このサイトでもっと質問する必要があります。
今後は、4 次元 kd ツリー、3 次元 kd ツリーに続く時間距離チェック (Drew Hall の提案)、および現在のアルゴリズムを含むいくつかのソリューションをテストする予定です。また、TSP (time space partitioning) ツリーと呼ばれる別のデータ構造が提案されています。これは、空間には octree を使用し、時間には各ノードの bsp を使用するので、それもテストする可能性があります。
私が覚えていると仮定すると、さまざまな時間/空間半径構成でいくつかのプロファイリング ベンチマークを必ず投稿します。
皆さんありがとう