Zオーダー曲線

Z オーダー曲線の反復が 3 次元に拡張されました。

数学的解析とコンピュータサイエンスにおいて、Z順序、ルベーグ曲線、モートン空間充填曲線、^[1] モートン順序またはモートンコードは、データポイントの局所性（多次元で互いに近い2つの点が高い確率で存在する場合、モートン順序でも互いに近い）をよく保存しながら、多次元データを1次元にマッピングする関数である。これは、フランスでは1904年にこれを研究したアンリ・ルベーグにちなんで名付けられ、 ^[2]米国では1966年にこの順序をファイルの順序付けに初めて適用したガイ・マクドナルド・モートンにちなんで名付けられた。^[3]多次元における点のZ値は、その座標値のバイナリ表現をインターリーブするだけで計算される。データがこの順序にソートされると、単純な1次元配列、二分探索木、B木、スキップリスト、または（下位ビットが切り捨てられた）ハッシュテーブルなど、任意の1次元データ構造を使用できるようになる。結果として得られる順序は、四分木または八分木の深さ優先走査から得られる順序と同等に記述できます。

座標値

z値 2479のインターリーブされたビットからZ 順序曲線 ( x、y ) 座標を計算します。

下の図は、整数座標 0 ≤ x ≤ 7、0 ≤ y ≤ 7の 2 次元の場合の Z 値を示しています (10 進数と 2 進数の両方で表示)。2 進座標値をインターリーブすると( xビット (青)で右から開始し、 yビット (赤)で交互に左に進む)、2 進z値が生成されます (図のように 45° 傾斜しています)。z 値を数値順に接続すると、再帰的にZ字型の曲線が生成されます。2 次元の Z 値は、クアッドキー値とも呼ばれます。

x座標のZ値は、モーザー・デ・ブリュイン数列の2進数として表され、偶数位置にのみ非ゼロのビットを持ちます。

x[] = {0b000000、0b000001、0b000100、0b000101、0b010000、0b010001、0b010100、0b010101}

2 つのx値の合計と差は、ビット演算を使用して計算されます。

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101
x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101 i ≥ jの場合

このプロパティは、Z 値をオフセットするために使用できます。たとえば、2 次元では、現在の Z 値 z から上 (y の減少)、下 (y の増加)、左 (x の減少)、右 (x の増加) への座標は次のようになります。

トップ = (((z & 0b10101010) − 1) & 0b10101010) | (z & 0b01010101)
下 = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)
左 = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010)
右 = (((z | 0b10101010) + 1) & 0b01010101) | (z & 0b10101010)

一般に、2つの2次元Z値 wと zを加算すると次のようになります。

合計 = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)

四分木と八分木を効率的に構築する

Z 順序付けは、点の集合に対して4 分木(2D) または8 分木(3D) を効率的に構築するために使用できます。 ^[4]^[5] 基本的な考え方は、入力セットを Z 順序に従ってソートすることです。ソートされると、点はバイナリ検索ツリーに格納されて直接使用されるか (線形 4 分木と呼ばれます)、^[6]ポインターベースの 4 分木を構築するために使用できます。

入力ポイントは通常、各次元で正の整数になるようにスケーリングされ、単位範囲[0, 1]の固定小数点表現として、またはマシンワードサイズに対応します。両方の表現は同等であり、定数時間で最上位の非ゼロビットを見つけることができます。四分木の各正方形は、2 の累乗である辺の長さと、辺の長さの倍数であるコーナー座標を持ちます。任意の 2 つのポイントが与えられた場合、 2 つのポイントの派生正方形は、両方のポイントをカバーする最小の正方形です。各ポイントのxおよびyコンポーネントからのビットのインターリーブは、xとyのシャッフルと呼ばれ、高次元に拡張できます。^[4]

ビットを明示的にインターリーブしなくても、ポイントはシャッフルに従ってソートできます。これを行うには、各次元について、その次元の 2 つのポイントの座標の排他的論理和の最上位ビットを調べます。次に、最上位ビットが最大である次元を使用して 2 つのポイントを比較し、シャッフル順序を決定します。

排他的論理和演算は、2 つの座標が同一である上位ビットをマスクします。シャッフルは上位ビットから下位ビットへとビットをインターリーブするため、最大の最上位ビットを持つ座標を識別すると、シャッフル順序で異なる最初のビットが識別され、その座標を使用して 2 つのポイントを比較できます。^[7] これは次の Python コードに示されています。

def  cmp_zorder ( lhs ,  rhs )  ->  bool : 
"""z 順序を比較します。""" # lhs と rhs をインデックスの配列のようなオブジェクトと想定します。assert len ( lhs ) == len ( rhs ) # 最も重要な次元が含まれます。msd = 0 # 他の次元をループします。for dim in range ( 1 , len ( lhs )): #最上位ビットを比較して、現在の次元の方が重要であるかどうかを確認します。 if less_msb ( lhs [ msd ] ^ rhs [ msd ], lhs [ dim ] ^ rhs [ dim ]): msd = dim return lhs [ msd ] < rhs [ msd ]

最上位ビットが小さいかどうかを判断する1つの方法は、各ポイントの2を底とする対数の底値を比較することです。次の操作は同等であり、排他的論理和演算のみが必要であることがわかります。^[7]

def  less_msb ( x :  int ,  y :  int )  ->  bool : 
    x < yかつx < ( x ^ y )を返します

同じ手法で浮動小数点数を比較することも可能です。関数less_msbは最初に指数を比較するように変更されます。指数が等しい場合にのみ、less_msb仮数部に標準関数が使用されます。^[8]

ポイントがソート順になると、2 つの特性により四分木の構築が容易になります。1 つ目は、四分木の正方形に含まれるポイントが、ソート順で連続した間隔を形成することです。2 つ目は、正方形の複数の子に入力ポイントが含まれる場合、その正方形はソート順で隣接する 2 つのポイントの派生正方形であることです。

隣接する点のペアごとに、派生した正方形が計算され、その辺の長さが決定されます。派生した正方形ごとに、それを含む区間は、ソート順で右と左にある最初の大きな正方形によって区切られます。^[4] このような各区間は、4分木の正方形に対応します。この結果、入力点または2つ以上の子を含むノードのみが存在する圧縮された4分木が作成されます。必要に応じて、欠落しているノードを復元することで、非圧縮の4分木を構築できます。

ポインタベースの四分木を構築する代わりに、ポイントは二分探索木などのデータ構造でソートされた順序で維持することができます。これにより、ポイントの追加と削除をO (log n )時間で行うことができます。2 つの四分木は、2 つのソートされたポイントセットをマージし、重複を削除することでマージできます。ポイントの位置は、ソートされた順序でクエリポイントの前後のポイントを検索することで実行できます。四分木が圧縮されている場合、見つかった先行ノードは、圧縮された対象のノード内の任意のリーフである可能性があります。この場合、クエリポイントと見つかったリーフの最小共通祖先の先行ノードを見つける必要があります。^[9]

範囲検索のための1次元データ構造で使用する

ビットインターリーブにより、データベースレコードは (おそらく非常に長い) ビットシーケンスに変換されます。ビットシーケンスは 2 進数として解釈され、データは、導入部で述べたように、任意の 1 次元データ構造を使用して、2 進値で並べ替えられるか、インデックスが付けられます。ただし、これらのデータで多次元検索範囲をクエリする場合、バイナリ検索を使用するのは実際には効率的ではありません。Z オーダーは局所性を適切に保持しますが、効率的な範囲検索には、データ構造で検出されたポイントから、多次元検索範囲内の次の可能な Z 値を計算するアルゴリズムが必要です。

この例では、クエリ対象の範囲 ( x = 2, ..., 3, y = 2, ..., 6) が点線の四角で示されています。その最高 Z 値 (MAX) は 45 です。この例では、Z 値の増加方向にデータ構造を検索しているときに値F = 19 に遭遇するため、 Fと MAX の間の区間 (斜線領域) を検索する必要があります。検索を高速化するには、検索範囲内の次の Z 値 (BIGMIN という例では 36) を計算し、BIGMIN と MAX の間の区間 (太字の値) のみを検索して、斜線領域の大部分をスキップします。減少方向に検索することは、クエリ範囲内でFより低い最高 Z 値である LITMAX に類似しています。BIGMIN 問題は Tropf と Herzog によって初めて提唱され、その解決策が示されました。^[10]出版後の履歴については、^{[11]を参照してください。}

LITMAX/BIGMIN 計算アルゴリズムの詳細な説明は、Pascal ソースコード (3D、nD に簡単に適応可能) および浮動小数点データと場合によっては負のデータを処理する方法に関するヒントとともに、2021 年に Tropf によって提供されています。ここでは、ビットインターリーブは明示的に行われません。データ構造には、元の (ソートされていない) データベースレコードへのポインターのみが含まれます。一般的なレコード比較関数 (z 値の意味で、大きい、小さい、等しい) を使用すると、ビットシーケンスの長さがコンピューターのワード長を超えるという複雑さが回避され、コードは任意の数の次元と任意のレコードキーワード長に簡単に適応できます。

このアプローチは選択された1次元データ構造に依存しないため、データの構造化を自由に選択することができ、バランスツリーなどのよく知られた方法を使用して動的データに対処することができ、挿入または削除時にツリーのバランスを維持するのにO(log n)の時間がかかります。この方法はUBツリー（バランス）でも使用されています^[12]。

自由選択により、既存のデータベースにメソッドを組み込むことが容易になります。これは、たとえば特別な考慮が必要となるR ツリーとは対照的です。

この方法を階層的に（手元のデータ構造に従って）適用すると、オプションで増加方向と減少方向の両方で、非常に効率的な多次元範囲検索が得られます。これは、たとえば最近傍検索の基礎となる手順として、商用および技術アプリケーションの両方で重要です。Zオーダーは、商用データベースシステムに採用されている数少ない多次元アクセス方法の1つです。^{[13]この方法は、さまざまな分野のさまざまな技術アプリケーション}^[14]や商用データベースシステムで使用されています。 ^[15]

1966 年というかなり昔に、GM モートンは静的な 2 次元地理データベースのファイル順序付けに Z オーダーを提案しました。エリアデータユニットは、そのサイズと右下隅の Z 値によって表される 1 つまたは複数の二次元のフレームに含まれており、サイズはコーナー位置の Z オーダー階層に準拠しています。隣接するフレームへの変更は、1 つまたはいくつかの比較的小さなスキャンステップで高い確率で実行されます。^[3]

アプリケーション

線形代数

行列乗算のシュトラッセンアルゴリズムは、行列を 4 つのブロックに分割し、各ブロックを 4 つの小さなブロックに再帰的に分割して、ブロックが 1 つの要素になるまで (またはより実際的には、モーザー・デ・ブリュインシーケンス自明アルゴリズムが高速になるくらい小さい行列に達するまで) 処理するものです。行列要素を Z オーダーで配置すると、局所性が向上し、さらに (行優先または列優先の順序と比較して) 2 つのブロックを乗算するサブルーチンは、行列の合計サイズを知る必要がなく、ブロックのサイズとメモリ内の位置だけを知ればよいという利点もあります。Z オーダーでのシュトラッセン乗算の効果的な使用法は実証されています。Valsalam と Skjellum の 2002 年の論文を参照してください。^[17]

Buluçらは、非ゼロ要素をZ順序付けして並列行列ベクトル乗算を可能にする疎行列データ構造を提示した。 ^[18]

線形代数の行列も空間充填曲線を使って走査することができる。^[19]従来のループは行列を行ごとに走査する。Z曲線を使った走査はメモリ階層への効率的なアクセスを可能にする。^[20]

テクスチャマッピング

一部のGPU はテクスチャマップをZ オーダーで保存し、テクスチャマップラスタライズ中に参照の空間的局所性を高めます。これにより、キャッシュラインが長方形のタイルを表すことができるため、近くのアクセスがキャッシュ内にある可能性が高まります。さらに大規模な場合、SDRAM/DDRAM でのコストのかかる、いわゆる「ページブレーク」(つまり、行を変更するコスト) の可能性も減ります。3D レンダリングには任意の変換 (回転、拡大縮小、遠近法、アニメーション化された表面による歪み) が含まれるため、これは重要です。

これらの形式は、スウィズルテクスチャまたはツイドルテクスチャと呼ばれることがよくあります。その他のタイル形式も使用される場合があります。

ん-体の問題

Barnes -Hutアルゴリズムでは、八分木の構築が必要です。データをポインタベースのツリーとして保存するには、八分木を深さ優先で反復処理するために、多くの連続したポインタ参照が必要です（分散メモリマシンではコストがかかります）。代わりに、八分木ハッシュを使用してハッシュテーブルにデータを保存すると、Zオーダー曲線は自然に八分木を深さ優先で反復処理します。^[5]

参照

参考文献

^ 離散グローバルグリッドシステム概要仕様(PDF)、Open Geospatial Consortium、2017
^ ドゥグンジ、ジェームズ（1989）、ウィリアム・C・ブラウン（編）、トポロジー、デュビューク（アイオワ州）、p. 105、ISBN 0-697-06889-7
^ ab Morton, GM (1966)、「コンピュータ指向の測地データベースとファイルシーケンスの新技術」(PDF)、技術レポート、オタワ、カナダ: IBM Ltd.
^ abc Bern, M.; Eppstein, D. ; Teng, S.-H. (1999)、「並列四分木の構築と高品質の三角測量」、Int. J. Comput. Geom. Appl.、9 (6): 517–532、CiteSeerX 10.1.1.33.4634、doi :10.1142/S0218195999000303 。
^ abc Warren, MS; Salmon, JK (1993)、「並列ハッシュ八分木 N 体アルゴリズム」、1993 ACM/IEEE スーパーコンピューティング会議議事録 - Supercomputing '93、ポートランド、オレゴン州、米国: ACM Press、pp. 12–21、doi : 10.1145/169627.169640、ISBN 978-0-8186-4340-8、S2CID 7583522
^ Gargantini, I. (1982)、「四分木を表現する効果的な方法」、Communications of the ACM、25 (12): 905–910、doi : 10.1145/358728.358741、S2CID 14988647。
^ ab Chan, T. (2002)、「RAM 上で簡略化された最近点問題」、ACM-SIAM 離散アルゴリズムシンポジウム。
^ Connor, M.; Kumar, P (2009)、「点群の k 近傍グラフの高速構築」、IEEE Transactions on Visualization and Computer Graphics (PDF) 、 2011-08-13 のオリジナル(PDF)からアーカイブ
^ Har-Peled, S. (2010)、幾何学的近似のためのデータ構造(PDF)
^ トロップ、H.; Herzog, H. (1981)、「動的にバランスの取れたツリーにおける多次元範囲検索」(PDF)、Angewandte Informatik、2 : 71–77。
^ https://hermanntropf.de/media/Z-Curve_LITMAX_BIGMIN_History_and_Applications_en.pdf
^ Ramsak, Frank; Markl, Volker ; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (2000)、「UB ツリーをデータベースシステムカーネルに統合する」、Int. Conf. on Very Large Databases (VLDB) (PDF) 、pp. 263–272、2016年 3 月 4 日のオリジナル(PDF)からアーカイブ
^ https://dl.acm.org/doi/pdf/10.1145/280277.280279 Volker Gaede、Oliver Günther: 多次元アクセス方法。ACM コンピューティング調査、巻=30、号=2、ページ=170–231、1998 年。
^ Z オーダー範囲検索を使用した技術アプリケーションに関する研究論文の注釈付きリスト(PDF)
^ Zオーダー範囲検索を使用したデータベースへの研究論文の注釈付きリスト（PDF）
^ S2 ジオメトリ
^ Vinod Valsalam、Anthony Skjellum: 階層的抽象化、アルゴリズム、最適化された低レベルカーネルに基づく高性能行列乗算フレームワーク。並行性と計算:実践と経験 14(10): 805-839 (2002)[1][2]
^ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009)、「圧縮スパースブロックを使用した並列スパース行列ベクトルおよび行列転置ベクトル乗算」、ACM Symp. on Parallelism in Algorithms and Architectures (PDF)、CiteSeerX 10.1.1.211.5256
^ Martin Perdacher: 共有メモリ環境におけるキャッシュ局所性を改善するための空間充填曲線。博士論文、ウィーン大学 2020 年
^ Martin Perdacher、Claudia Plant、Christian Böhm: LU分解の例におけるモートン次数曲線を使用したデータ局所性の改善。IEEE BigData 2020: pp. 351–360

外部リンク

STANN: Zオーダー曲線を使用した近似最近傍検索用ライブラリ
ビットインターリーブのプログラミング方法、ショーン・エロン・アンダーソン、スタンフォード大学

[1] 離散グローバルグリッドシステム概要仕様(PDF)、Open Geospatial Consortium、2017

[2] ドゥグンジ、ジェームズ（1989）、ウィリアム・C・ブラウン（編）、トポロジー、デュビューク（アイオワ州）、p. 105、ISBN 0-697-06889-7

[morton1-3] Morton, GM (1966)、「コンピュータ指向の測地データベースとファイルシーケンスの新技術」(PDF)、技術レポート、オタワ、カナダ: IBM Ltd.

[parallel-4] Bern, M.; Eppstein, D. ; Teng, S.-H. (1999)、「並列四分木の構築と高品質の三角測量」、Int. J. Comput. Geom. Appl.、9 (6): 517–532、CiteSeerX 10.1.1.33.4634、doi :10.1142/S0218195999000303 。

[:0-5] Warren, MS; Salmon, JK (1993)、「並列ハッシュ八分木 N 体アルゴリズム」、1993 ACM/IEEE スーパーコンピューティング会議議事録 - Supercomputing '93、ポートランド、オレゴン州、米国: ACM Press、pp. 12–21、doi : 10.1145/169627.169640、ISBN 978-0-8186-4340-8、S2CID 7583522

[6] Gargantini, I. (1982)、「四分木を表現する効果的な方法」、Communications of the ACM、25 (12): 905–910、doi : 10.1145/358728.358741、S2CID 14988647。

[closest-7] Chan, T. (2002)、「RAM 上で簡略化された最近点問題」、ACM-SIAM 離散アルゴリズムシンポジウム。

[8] Connor, M.; Kumar, P (2009)、「点群の k 近傍グラフの高速構築」、IEEE Transactions on Visualization and Computer Graphics (PDF) 、 2011-08-13 のオリジナル(PDF)からアーカイブ

[9] Har-Peled, S. (2010)、幾何学的近似のためのデータ構造(PDF)

[10] トロップ、H.; Herzog, H. (1981)、「動的にバランスの取れたツリーにおける多次元範囲検索」(PDF)、Angewandte Informatik、2 : 71–77。

[11] ttps://hermanntropf.de/media/Z-Curve_LITMAX_BIGMIN_History_and_Applications_en.pdf

[12] Ramsak, Frank; Markl, Volker ; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (2000)、「UB ツリーをデータベースシステムカーネルに統合する」、Int. Conf. on Very Large Databases (VLDB) (PDF) 、pp. 263–272、2016年 3 月 4 日のオリジナル(PDF)からアーカイブ

[13] ttps://dl.acm.org/doi/pdf/10.1145/280277.280279 Volker Gaede、Oliver Günther: 多次元アクセス方法。ACM コンピューティング調査、巻=30、号=2、ページ=170–231、1998 年。

[14] Z オーダー範囲検索を使用した技術アプリケーションに関する研究論文の注釈付きリスト(PDF)

[15] Zオーダー範囲検索を使用したデータベースへの研究論文の注釈付きリスト（PDF）

[16] S2 ジオメトリ

[17] Vinod Valsalam、Anthony Skjellum: 階層的抽象化、アルゴリズム、最適化された低レベルカーネルに基づく高性能行列乗算フレームワーク。並行性と計算:実践と経験 14(10): 805-839 (2002)[1][2]

[18] Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009)、「圧縮スパースブロックを使用した並列スパース行列ベクトルおよび行列転置ベクトル乗算」、ACM Symp. on Parallelism in Algorithms and Architectures (PDF)、CiteSeerX 10.1.1.211.5256

[19] Martin Perdacher: 共有メモリ環境におけるキャッシュ局所性を改善するための空間充填曲線。博士論文、ウィーン大学 2020 年

[20] Martin Perdacher、Claudia Plant、Christian Böhm: LU分解の例におけるモートン次数曲線を使用したデータ局所性の改善。IEEE BigData 2020: pp. 351–360

座標値