22

空間インデックスを一括読み込みするために、ヒルベルト次数で d 次元のデータ ベクトルを並べ替えようとしています。

ただし、各点のヒルベルト値を明示的に計算したくはありません。特に、特定の精度を設定する必要があります。高次元データでは、これには32*dビットなどの精度が含まれ、効率的に行うには非常に面倒です。データが不均一に分布している場合、これらの計算の一部は不要であり、データ セットの一部に特別な精度が必要になります。

代わりに、パーティショニング アプローチを実行しようとしています。2次元の一次ヒルベルト曲線を見ると

1   4
|   |
2---3

まず x 軸に沿ってデータを分割し、最初の部分 (必ずしもオブジェクトの半分を含むとは限りません!) が 1 と 2 (まだソートされていない) で構成され、2 番目の部分が 3 と 4 のオブジェクトを持つようにします。それだけ。次に、Y 軸で各半分をもう一度分割しますが、順序を 3-4 に逆にします。

したがって、基本的には、分割統治戦略 (QuickSort と密接に関連しています。均等に分散されたデータでは、これは最適であるはずです!) を実行し、必要に応じてヒルベルト インデックスの必要な「ビット」のみを計算します。したがって、「1」に単一のオブジェクトがあると仮定すると、その完全な表現を計算する必要はありません。オブジェクトが均等に分散されている場合、パーティションのサイズはすぐに減少します。

私は、長いグレーコーディングの次元インターリーブに変換する通常の教科書的なアプローチを知っています。これは私が探しているものではありません (利用可能な例はたくさんあります)。私は明示的に遅延分割統治ソートのみを望んでいます。さらに、2D 以上が必要です。

このように機能する記事またはヒルベルトソートアルゴリズムを知っている人はいますか? または、「回転」を正しく行う方法、どの表現を選択するかという重要なアイデアはありますか? 特に高次元では... 2Dでは些細なことです。1 は +y、+x の回転、4 は -y、-x (回転と反転) です。しかし、より高い次元では、これはよりトリッキーになると思います。

(もちろん、結果は、オブジェクトをヒルベルト次数で十分に大きな精度でソートした場合と同じになるはずです。必要のないときに完全な表現を計算し、それを管理する時間を節約しようとしているだけです。多くの人々は、かなり高価な「ヒルベルト数へのオブジェクト」ハッシュマップを保持しています。)

Peano 曲線と Z 曲線についても同様のアプローチが可能であり、おそらく実装が少し簡単です...おそらく最初にこれらを試す必要があります (Z 曲線は既に機能しています。仮想ピボットとしての適切な平均/グリッド値と各反復の次元の循環)。

編集：Zおよびpeano曲線でどのように解決したかについては、以下を参照してください。また、すでに 2D ヒルベルト曲線に対しても機能しています。しかし、ヒルベルト曲線の回転と反転はまだ正しくありません。

4

3 に答える 3

7

基数ソートを使用します。各1次元インデックスをd .. 32、それぞれサイズ1 .. 32/dビットのパーツに分割します。次に、（上位ビットから下位ビットまで）各インデックスピースについて、ヒルベルト値を計算し、オブジェクトを適切なビンにシャッフルします。

これは、ヒルベルト順序またはZ順序の両方で、均等に分散されたデータと不均一に分散されたデータの両方でうまく機能するはずです。また、多精度の計算は必要ありません。

インデックスピースをヒルベルト順序に変換する方法の詳細：

  • 最初に必要なビットを抽出し、
  • 次に、すべての次元のビットをインターリーブします。
  • 次に、1次元インデックスを逆グレイコードに変換します。

インデックスがdoubleに格納されている場合：

  • インデックスが負の場合は、値を追加してすべてを正にし、タスクを簡素化します。
  • すべてのインデックスよりも大きい2の最小の整数乗を決定し、すべてのインデックスをこの値に分割します
  • インデックスを2^（現在のソートステップに必要なビット数）に乗算します。結果を切り捨て、整数に変換し、ヒルベルトの順序付けに使用します（インターリーブして逆グレイコードを計算します）
  • 前のステップで切り捨てられた結果をインデックスから減算します。index = index - i

d基数ソートのバリアントについては、サイズの2つのバイナリ配列（1つは主にスタックとして使用され、もう1つはインデックスビットの反転に使用される）と回転値（zsortからhilbertsortを作成するため）を拡張することをお勧めします。寸法を再配置するために使用されます）。

スタックの最上位値が1の場合、pivotize（...昇順）をpivotize（...降順）に変更し、再帰の最初の部分では、この最上位値をスタックにプッシュし、2番目の部分ではプッシュします。この値の逆。このスタックは、再帰するたびに復元する必要があります。dこれには、基数ソート手順の最後の再帰の「決定木」が含まれています（逆グレイコード）。

再帰後d、この「決定木」スタックを使用して、回転値と反転の配列の両方を再計算する必要があります。それを行う正確な方法は簡単ではありません。次のリンクにあります：hilbert.cまたはhilbert.c。

于 2011-12-13T12:12:52.687 に答える
2

再帰、L-システム、または分割統治法を使用せずに、f(x)=y からヒルベルト曲線を直接計算できます。基本的には、グレー コードまたはハミルトニアン パス トラバーサルです。Nick の空間インデックス ヒルベルト カーブ クワッドツリー ブログまたは本のハッカーズ デライトで適切な説明を見つけることができます。または、単調なn-aryグレイコードを見てください。ムーア曲線を含む実装を php で作成しました。

于 2011-12-13T01:49:49.500 に答える
0

私はすでにこの質問 (および他の質問) に回答しましたが、回答が不思議なことに消えてしまいました。http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/CompactHilbertCurve.javaからのコンパクト ヒルベルト インデックスの実装(メソッド index() ) では、計算されるヒルベルト インデックスのビット数を特定のレベルまで制限することができます。上記のメソッドからのループの各反復は、空間の次元に等しい数のビットを計算します。一度に 1 つのレベル (つまり、空間の次元に等しいビット数) だけを計算するように for ループを簡単にリファクタリングできます。コンパクト ヒルベルト インデックスによって辞書式に 2 つの数値を比較するのに必要な深さだけに進みます。

于 2012-03-29T12:03:22.737 に答える