PH-tree
PH-tree
タイプツリー、マップ
発明2014
ビッグO記法による時間計算量
操作平均最悪の場合
検索 O( log n ) O( log n )
入れる O( log n ) O( log n )
削除 O( log n ) O( log n )
空間計算量
空間 O( n ) O( n )

PH木[ 1 ]は、地理​​座標、点、特徴ベクトル、長方形、境界ボックスなどの多次元データ（キー）の空間インデックス作成に使用されるツリーデータ構造です。PH木は、四分木や八分木に似た構造を持つ空間分割インデックス[ 2 ]です。[ 3 ]ただし、四分木とは異なり、トライに基づく分割ポリシーを使用し、キーのビット表現に基づくCritビット木に似ています。ビットベースの分割ポリシーは、ノードの異なる内部表現の使用と組み合わせることで、高次元データでスケーラビリティを提供します。ビット表現の分割ポリシーでは最大深度も課されるため、ツリーの退化や再バランス調整の必要性を回避できます。[ 1 ]

概要

基本的なPH木は、整数を持つd次元ベクトルであるキーをユーザー定義の値にマッピングする空間インデックスです。PH木は、 Critビット木がd次元キーを持つPH木と同等であるという意味で、Critビット木の多次元一般化です。Critビット木と同様に、そして他のほとんどの空間インデックスとは異なり、PH木はマルチマップではなくマップです。[ 1 ] [ 4 ]1{\displaystyle 1}

d次元PH木は、各ノードが空間を象限に分割するノードツリーです（潜在的に大きなノードが高次元データでどのように拡張されるかについては後述）。各象限には、キーと値のペア（リーフ象限）またはキーとサブノードのペアのいずれか、最大1つのエントリが含まれます。キーとサブノードのペアの場合、キーはサブノードの中心を表します。キーは、サブノードとその子サブノードのすべてのキーの共通のプレフィックス（ビット表現）でもあります。各ノードは少なくとも2つのエントリを持ち、そうでない場合は親ノードとマージされます。[ 1 ]2d{\displaystyle 2^{d}}

PH木のその他の構造的特性は以下の通りである: [ 1 ]

  • それらは-ary木です。2n{\displaystyle 2^{n}}
  • これらは本質的に不均衡ですが、深さがキーのビット幅に制限されるため、不均衡は制限されます。たとえば、32 ビット整数の - 次元キーの場合は 32 になります。d{\displaystyle d}
  • 挿入または削除操作は、正確に1つのノードを変更し、場合によっては2つ目のノードを追加または削除します。これは、同時実装に便利です。また、変更コストの変動もほとんどありません。
  • それらの構造は挿入/削除の順序に依存しません。

分割戦略

ほとんどの四分木と同様に、PH木はノードの階層構造であり、各ノードはすべてのd次元で空間を分割します。[ 1 ]したがって、ノードは各象限に1つずつ、最大でサブノードを 持つことができます2d{\displaystyle 2^{d}}

ビット文字列によるハイパーキューブアドレッシング

象限番号

PH木は、多次元キーのビットを使用して、木内の位置を決定します。同じ先頭ビットを持つすべてのキーは、木の同じ枝に格納されます。[ 1 ]

例えば、レベルLのノードでは、キーを挿入（または削除、あるいは検索）する象限を決定するために、キーの各次元のLビットを参照します。8つの象限を持つ3Dノード（立方体を形成）の場合、キーの最初の次元のLビットは対象の象限が立方体の左側か右側かを判断し、 2番目の次元のLビットは対象の象限が前面か背面かを判断し、3番目の次元の Lビットは下面か上面かを判断します（図を参照）。

3つのキーを追加して2つのノードを持つPHツリーの例。ルートノード（赤）とサブノード（青）。

1次元の例

8ビット値を持つ3つの1次元キー（、、 ）の例。空の木にとを追加すると、1つのノードが生成されます。2つのキーはまず6番目のビットが異なるため、ノードにはレベル（0から始まる）があります。ノードには、両方のキーに共通する5ビットを表す5ビットのプレフィックスがあります。ノードには2つの象限があり、各キーは一方の象限に格納されます。3つ目のキーを追加すると、に1つの追加ノードが生成され、一方の象限には元のノードがサブノードとして含まれ、もう一方の象限には新しいキーが含まれます k0＝{1}base 10＝{00000001}base 2{\displaystyle k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}}k1＝{4}10＝{00000100}2{\displaystyle k_{1}=\{4\}_{10}=\{00000100\}_{2}}k2＝{35}10＝{00100011}2{\displaystyle k_{2}=\{35\}_{10}=\{00100011\}_{2}}k0{\displaystyle k_{0}}k1{\displaystyle k_{1}}L＝5{\displaystyle L=5}k3{\displaystyle k_{3}}L＝2{\displaystyle L=2}k2{\displaystyle k_{2}}

1つのノードに2つの2Dキーを持つPHツリーの例

2Dの例

2次元キーでは、すべてのノードは象限を持ちます。キーが格納されている象限の位置は、キーの各ビット（各次元から1ビットずつ）から抽出されます。ノードの4つの象限は2次元ハイパーキューブを形成します（象限が空の場合もあります）。キーから抽出されたビットは、、、 のハイパーキューブアドレスを形成します。これは、実質的にノードのハイパーキューブにおける象限の位置です。 2d＝4{\displaystyle 2^{d}=4}h{\displaystyle h}k0→h＝{00}2{\displaystyle k_{0}\rightarrow h=\{00\}_{2}}k1→h＝{01}2{\displaystyle k_{1}\rightarrow h=\{01\}_{2}}h{\displaystyle h}

ノード構造

ノード内のエントリの順序は常にZオーダーに従います。例えば、ノード内のエントリはサイズ の固定サイズの配列に格納できます。hは実質的に象限の配列インデックスとなります。これにより、 による検索、挿入、削除が可能になり、 h を格納する必要はありません。ただし、空間計算量はノードごとに であるため、高次元データには適していません。[ 1 ]2d{\displaystyle 2^{d}}O（1）{\displaystyle O(1)}O（2d）{\displaystyle O(2^{d})}

もう一つの解決策は、動的配列やB木などのソートされたコレクションにエントリを格納することです。これにより、検索操作は遅くなりますが、メモリ消費は少なくなります。[ 1 ]O（ログ⁡nnode_entries）{\displaystyle O(\log {n_{node\_entries}})}O（nnode_entries）{\displaystyle O(n_{node\_entries})}

オリジナルの実装では、メモリ消費量が少ない方に応じて固定配列と動的配列の表現を切り替えることで、メモリ消費を最小限に抑えることを目指していました。[ 1 ]他の実装[1] [2]では、動的に切り替えず、には固定配列、には動的配列、高次元データにはBツリーを使用します。 d≲4{\displaystyle d\lesssim 4}d≲8{\displaystyle d\lesssim 8}

操作

検索、挿入、削除の操作はすべて非常によく似ています。正しいノードを見つけ、そのノードに対して操作を実行します。ウィンドウクエリとk近傍検索はより複雑です

ルックアップ

ルックアップ操作は、ツリー内にキーが存在するかどうかを判断します。ツリーを辿り、すべてのノードに候補となるサブノードまたはキーに一致するユーザー値が含まれているかどうかを確認します。[ 1 ]

関数lookup(key)は entry ← get_root_entry() // ツリーが空でない場合、ルートエントリにはルートノードが含まれます entry != NIL && entry.is_subnode()の場合、 ノード ← entry.get_node() エントリ ← node.get_entry(キー) 繰り返してエントリを返す// エントリはNILになる可能性がある 
関数get_entry(key)は ノード ← 現在のノード h ← extract_bits_at_depth(キー、node.get_depth()} エントリ ← node.get_entry_at(h) エントリを返す// エントリはNILになる可能性がある

入れる

挿入操作は、キーが既に存在しない限り、新しいキーと値のペアをツリーに挿入します。この操作は、Lookup関数のようにツリーを走査し、キーをノードに挿入します。考慮すべきケースがいくつかあります。[ 1 ]

  1. 象限は空なので、象限に新しいエントリを挿入して戻るだけです。
  2. 象限には、新しいエントリと同一のキーを持つユーザーエントリが含まれています。このような衝突に対処する方法の一つは、挿入に失敗したことを示すフラグを返すことです。ツリーがマルチマップとして実装され、コレクションがノードのエントリとして定義されている場合、新しい値はそのコレクションに追加されます。
  3. 象限に異なるキーを持つエントリ（ユーザーエントリまたはサブノードエントリ）が含まれています。この場合、既存のエントリを、古いエントリと新しいエントリの両方を保持する新しいサブノードに置き換える必要があります。
関数insert(ノード, キー, 値) level ← node.get_level() // ルートのレベルは0 h ← extract_bits_at_level(キー, レベル) エントリ ← node.get_entry(h) エントリ == NILの場合 // ケース1。 entry_new ← create_entry(キー, 値) node.set_entry(h, entry_new) そうでなければ、!entry.is_subnode() && entry.get_key() == keyの場合 // ケース2. 衝突、すでにエントリがある 戻り値← failed_insertion else // ケース3。 レベル差 ← 差異レベルを取得(キー、エントリ.get_key()) entry_new ← create_entry(キー, 値) // 既存のエントリと新しいエントリを含む新しいサブノード subnode_new ← create_node(level_diff, entry, entry_new) node.set_entry(h, サブノードの新しい) 終了ifリターン

削除

削除は挿入とは逆に動作しますが、残っているエントリが2つ未満の場合はサブノードを削除しなければならないという制約が追加されます。残っているエントリは親ノードに移動されます。[ 1 ]

ウィンドウクエリ

ウィンドウクエリは、長方形の軸に沿ったハイパーボックス内にあるすべてのキーを返すクエリです。これらは2つのd次元点として定義でき、クエリボックスの「左下」と「右上」の角を表します。簡単な実装では、ノード内のすべてのエントリ（ルートノードから開始）を走査し、エントリが一致した場合は、それを結果リストに追加するか（ユーザーエントリの場合）、再帰的に走査します（サブノードの場合）。[ 1 ]min{\displaystyle min}max{\displaystyle max}

関数query(node, min, max, result_list)は、foreach entry ← node.get_entries()を実行し 、 entry.is_subnode()の場合は 、entry.get_prefix() >= min かつ entry.get_prefix() <= maxの場合は、 クエリ(entry.get_subnode(), 最小値, 最大値, 結果リスト) 終了 if else if entry.get_key() >= min かつ entry.get_key() <= max then result_list.add(エントリ) end if end if繰り返しreturn

クエリの時間計算量を正確に推定するには、次元を考慮した分析が必要です。ノード内のすべてのエントリを走査して比較するには、次元キーとの比較にそれぞれ時間がかかるため、時間計算量は となります。ノードは最大 エントリを持つことができるため、次元数の増加に伴ってスケーリングが困難になります。このアプローチは、ハイパーキューブアドレスhを利用することで改善できる様々な方法があります。[ 4 ]d{\displaystyle d}nnode_entries{\displaystyle n_{node\_entries}}O(d⋅nnode_entries){\displaystyle O(d\cdot n_{node\_entries})}d{\displaystyle d}min/max{\displaystyle min/max}O(d){\displaystyle O(d)}2d{\displaystyle 2^{d}}d{\displaystyle d}

最小時間と最大時間

アイデアは、検索ボックスと重ならない象限をいくつか回避しながら、象限のアドレスの最小値と最大値を求めることです。をノードの中心（これはノードのプレフィックスに等しい）とし、と をそれぞれ ビットの2つのビット文字列とします。また、 の添え字は と の ビット、の 次元、を表します。h{\displaystyle h}C{\displaystyle C}hmin{\displaystyle h_{min}}hmax{\displaystyle h_{max}}d{\displaystyle d}i{\displaystyle i}0≤i<d{\displaystyle 0\leq i<d}i{\displaystyle i}hmin{\displaystyle h_{min}}hmax{\displaystyle h_{max}}i{\displaystyle i}min{\displaystyle min}max{\displaystyle max}C{\displaystyle C}

と とすると、は、ノードの「下」半分とその中のすべての象限がクエリボックスと重ならないすべての次元に対して` ` を持ちます。同様に、 は、ノードの「上」半分がクエリボックスと重ならないすべての次元に対して ` ` を持ちます。hmin,i=(mini≤Ci){\displaystyle h_{min,i}=(min_{i}\leq C_{i})}hmax,i=(maxi≥Ci){\displaystyle h_{max,i}=(max_{i}\geq C_{i})}hmin{\displaystyle h_{min}}1{\displaystyle 1}hmin{\displaystyle h_{min}}0{\displaystyle 0}

hmin{\displaystyle h_{min}}そして、通過する必要があるノードの最低値と最高値を提示します。クエリボックスと交差する象限、または交差しない象限。証明は[ 4 ]で入手できます。これにより、上記のクエリ関数は次のように改善できます。 hmax{\displaystyle h_{max}}h{\displaystyle h}h<hmin{\displaystyle h<h_{min}}h>hmax{\displaystyle h>h_{max}}

関数query(node, min, max, result_list)は h_min ← h_minを計算する h_max ← h_maxを計算する 各エントリに対して ← node.get_entries_range(h_min, h_max)を実行します [ ... ] 繰り返して戻る

とを計算すると…です。ノード内の占有象限の分布に応じて、このアプローチにより、キーの比較を全く回避できないか、ほぼすべて回避できます。これにより平均走査時間は短縮されますが、結果として生じる複雑さは依然として…です。[ 4 ]hmin{\displaystyle h_{min}}hmax{\displaystyle h_{max}}O(2d)=O(d){\displaystyle O(2d)=O(d)}O(d+d⋅nnode_entries){\displaystyle O(d+d\cdot n_{node\_entries})}

クエリボックスとの重複がないか四分円をチェックする

と の間には、クエリ ボックスと重ならない象限が存在する可能性があります。アイデア:とはそれぞれ次元ごとに 1 ビットを持ち、クエリ ボックスがその次元のノードの下位半分/上位半分と重なっているかどうかを示します。これを使用すると、次元のキーを比較することなく、象限がクエリ ボックスと重なっているかどうかをすばやく確認できます。 のすべての ` ` ビットに対して に対応する ` ` ビットがあり、 のすべての ` ` ビットに対して に対応する ` ` ビットがある場合、象限はクエリ ボックスと重なっています。したがって、64 ビット レジスタを持つ CPU では、の最大次元のキーの重なりを確認することができます。[ 4 ]hmin{\displaystyle h_{min}}hmax{\displaystyle h_{max}}hmin{\displaystyle h_{min}}hmax{\displaystyle h_{max}}h{\displaystyle h}d{\displaystyle d}h{\displaystyle h}0{\displaystyle 0}h{\displaystyle h}0{\displaystyle 0}hmin{\displaystyle h_{min}}1{\displaystyle 1}h{\displaystyle h}1{\displaystyle 1}hmax{\displaystyle h_{max}}64{\displaystyle 64}O(1){\displaystyle O(1)}

function is_overlap(h, h_min, h_max) is return (h | h_min) & h_max == h // 象限とクエリが重複している場合は 'true' と評価されます。 
関数query(node, min, max, result_list)は h_min ← h_minを計算する h_max ← h_maxを計算する 各エントリに対して ← node.get_entries_range(h_min, h_max)を実行します h ← entry.get_h(); if (h | h_min) & h_max == h then // 象限とクエリが重複している場合は 'true' と評価されます。 [ ... ] 繰り返しの場合は終了、戻り

結果として得られる時間計算量は、完全な反復の計算量と比較される。[ 4 ]O(d+nnode_entries){\displaystyle O(d+n_{node\_entries})}O(d⋅nnode_entries){\displaystyle O(d\cdot n_{node\_entries})}

クエリボックスと重なる象限をトラバースする

より大きなノードを持つ高次元の場合、すべての反復処理を避け、クエリボックスと重なる次の高次元を直接計算することも可能です。最初のステップでは、クエリボックスと重ならないすべての象限について、 ` `ビットを所定の値に設定します。2番目のステップでは、適応された値をインクリメントし、追加された` `ビットによってオーバーフローがトリガーされるため、重ならない象限はスキップされます。最後のステップでは、オーバーフローのトリガーとして使用される不要なビットをすべて削除します。このロジックは[ 4 ]で詳細に説明されています。計算は次のように行われます。 h{\displaystyle h}h{\displaystyle h}1{\displaystyle 1}hinput{\displaystyle h_{input}}h{\displaystyle h}1{\displaystyle 1}

関数increment_h(h_input, h_min, h_max)は h_out = h_input | (~ h_max) // 事前マスク h_out += 1 // 増分 h_out = ( h_out & h_max ) | h_min // ポストマスク h_outを 返す

繰り返しますが、これはほとんどのCPUで で実行できます。ノードを走査するための結果として得られる時間計算量は です。[ 4 ]これは、クエリボックスと重なる象限のほとんどがエントリで占有されている場合に最もうまく機能します。 d≤64{\displaystyle d\leq 64}O(1){\displaystyle O(1)}O(d+noverlapping_quadrants){\displaystyle O(d+n_{overlapping\_quadrants})}

k近傍法

k近傍探索は標準的なアルゴリズムを使用して実装できます。 [ 5 ]

浮動小数点キー

PH木は整数値のみを格納できます。浮動小数点値は整数に変換することで簡単に整数として格納できます。しかし、著者らは精度を損なわないアプローチも提案しています。[ 1 ] [ 4 ]

ロスレス変換

浮動小数点値を整数値にロスレス変換（およびその逆変換）することで、精度を損なうことなく、浮動小数点値の32ビットまたは64ビットを整数（32ビットまたは64ビット）として解釈するだけで実現できます。IEEE 754が浮動小数点値をエンコードする方法により、結果の整数値は、少なくとも正の値については、元の浮動小数点値と同じ順序になります。負の値の順序は、非符号ビットを反転することで実現できます。[ 1 ] [ 4 ]

Javaでの実装例: 

long encode ( double値) { long r = Double . doubleToRawLongBits (値); return ( r >= 0 ) ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

C++での実装例: 

std :: int64_t encode ( double value ) { std :: int64_t r ; memcpy ( & r , & value , sizeof ( r )); return r >= 0 ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

エンコード（および逆デコード）は、すべての浮動小数点値に対してロスレスです。順序付けは実際には、や を含めてうまく機能します。しかし、整数表現も通常の比較可能な値（無限大より小さい）に変換され、無限大は互いに比較可能であり、は より大きいです。[ 6 ]つまり、例えば、クエリ範囲はの値と一致しません。 と一致させるには、クエリ範囲は である必要があります。 ±∞{\displaystyle \pm \infty }−0.0{\displaystyle -0.0}NaN{\displaystyle NaN}0.0{\displaystyle 0.0}−0.0{\displaystyle -0.0}[0.0,10.0]{\displaystyle [0.0,10.0]}−0.0{\displaystyle -0.0}−0.0{\displaystyle -0.0}[−0.0,10.0]{\displaystyle [-0.0,10.0]}

ハイパーボックスキー

ボリューム（軸に沿ったハイパーボックス）をキーとして保存するために、実装では通常、コーナー表現[ 7 ]が使用されます。コーナー表現は、ボックスの2次元の最小コーナーと最大コーナーを、たとえばインターリーブすることによって、次元を持つ単一のキーに変換します。 d{\displaystyle d}2d{\displaystyle 2d}k={min0,max0,min1,max1,...,mind−1,maxd−1}{\displaystyle k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}}

これは、検索、挿入、削除の各操作では簡単に機能します。ウィンドウクエリは、次元ベクトルから次元ベクトルに変換する必要があります。例えば、クエリボックス内に完全に収まるすべてのボックスに一致するウィンドウクエリの場合、クエリキーは次のようになります。[ 7 ] [ 8 ]d{\displaystyle d}2d{\displaystyle 2d}

kmin={min0,min0,min1,min1,...,mind−1,mind−1}{\displaystyle k_{min}=\{min_{0},min_{0},min_{1},min_{1},...,min_{d-1},min_{d-1}\}}

kmax={max0,max0,max1,max1,...,maxd−1,maxd−1}{\displaystyle k_{max}=\{max_{0},max_{0},max_{1},max_{1},...,max_{d-1},max_{d-1}\}}

クエリボックスと交差するすべてのボックスに一致するウィンドウクエリ操作の場合、クエリキーは次のようになります。[ 8 ]

kmin={−∞,min0,−∞,min1,...,−∞,mind−1}{\displaystyle k_{min}=\{-\infty ,min_{0},-\infty ,min_{1},...,-\infty ,min_{d-1}\}}

kmax={max0,+∞,max1,+∞,...,maxd−1,+∞}{\displaystyle k_{max}=\{max_{0},+\infty ,max_{1},+\infty ,...,max_{d-1},+\infty \}}

スケーラビリティ

エントリ数が少ない高次元では、PH木はノードを1つしか持たない可能性があり、実質的にZオーダー曲線を持つB木に「退化」します。追加/削除/検索操作はそのまま残り、ウィンドウクエリは象限フィルタを使用できます。ただし、これは次元の呪いを回避することはできません。高次元データまたはPH木はフルスキャンよりもわずかに優れているだけです。[ 9 ]2d{\displaystyle 2^{d}}O(log⁡n){\displaystyle O(\log {n})}d=50{\displaystyle d=50}d=100{\displaystyle d=100}

用途

研究では、大規模で急速に変化するデータセットに対して、高速な追加/削除/完全一致操作が報告されています。[ 10 ]ウィンドウクエリは、特に小さなウィンドウ[ 11 ]または大規模なデータセット[ 12 ]でうまく機能することが示されています

PH木は主にインメモリでの使用に適しています。[ 10 ] [ 13 ] [ 14 ] ノードのサイズ（エントリ数）は固定ですが、永続ストレージでは、ノードサイズをディスク上のページサイズに合わせるために、ノードサイズを設定できるインデックスが役立ちます。これは、R木などの他の空間インデックスを使用すると容易になります。

実装

参照

参考文献

  1. ^ a b c d e f g h i j k l m n o p Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (2014年6月). 「PH-tree」 . 2014 ACM SIGMOD International Conference on Management of Data の議事録. pp.  397– 408. doi : 10.1145/2588555.2588564 . ISBN 9781450323765. S2CID  6862850 . 2022年2月10日閲覧
  2. ^ Kouahla, Z.; Benrazek, A.-E.; Ferrag, MA; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). 「ビッグIoTデータのインデックス作成に関する調査：潜在的な解決策、最近の進歩、そして未解決の課題」 Future Internet . 14 (1): 19. doi : 10.3390/fi14010019 .
  3. ^ Mahmood, AR; Punni, S.; Aref, WG (2018). 「時空間アクセス方法：調査（2010～2017年）」. Geoinformatica . 23 (1): 1– 36. doi : 10.1007/s10707-018-0329-2 . S2CID 106407322 . 
  4. ^ a b c d e f g h i jゼシュケ、ティルマン;ノリー、モイラ (2017)。 「ハイパーキューブインデックスの効率的な Z オーダートラバーサル」。ビジネス、テクノロジー、ウェブのためのデータバンクシステム (BTW 2017)。情報学の講義ノート。 Vol. P-265。ボン: Gesellschaft für Informatik。 pp.  465–484 . doi : 10.3929/ethz-a-010802003。ISBN 9783885796596。
  5. ^ Hjaltason, Gísli R.; Samet, Hanan (1999年6月). 「空間データベースにおける距離ブラウジング」 . ACM Transactions on Database Systems . 24 (2): 265–318 . doi : 10.1145/320248.320255 . S2CID 10881319. 2022年2月12日閲覧 
  6. ^ IEEE 754 2019 harvnb error: no target: CITEREFIEEE_7542019 (help)
  7. ^ a b Seeger, B.; Kriegel, HP (1988). 「効率的な空間アクセス方式の設計と実装のための技術」. Proceedings 1988 VLDB Conference: 14th International Conference on Very Large Data Bases . 14 : 360.
  8. ^ a bサメット、ハナン (2006).多次元および計量データ構造の基礎サンフランシスコ: エルゼビア/モーガン・カウフマン. pp.  440– 441, 453– 457. ISBN 0-12-369446-9。
  9. ^ Li, Yan; Ge, Tingjian; Chen, Cindy (2020). 「ナレッジグラフにおける予測的トップkエンティティおよび集約クエリのためのオンラインインデックス」. 2020 IEEE 36th International Conference on Data Engineering (ICDE) . pp.  1057– 1068. doi : 10.1109/ICDE48307.2020.00096 . ISBN 978-1-7281-2903-7. S2CID  218907333 .
  10. ^ a b Sprenger, Stefan (2019).メインメモリにおける範囲クエリの効率的な処理（博士論文）. ベルリン・フンボルト大学. doi : 10.18452/19786
  11. ^ Khatibi, A.; Porto, F.; Rittmeyer, JG; Ogasawara, E.; Valduriez, P.; Shasha, D. (2017年8月). 「ビッグデータにおけるコンステレーションクエリの前処理とインデックス作成技術」.ビッグデータ分析と知識発見(PDF) . コンピュータサイエンス講義ノート. 第10440巻. pp.  164– 172. doi : 10.1007/978-3-319-64283-3_12 . ISBN 978-3-319-64282-6. S2CID  3857469 .
  12. ^ Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, ET; Neumann, T.; Kemper, A. (2020). 「データベース技術」. GeoBlocks: ポリゴン上の空間集約のためのクエリキャッシュ高速化データ構造. 第23巻. OpenProceedings.org. pp.  169– 180. doi : 10.5441/002/ edbt.2021.16
  13. ^ Wang, S.; Maier, D.; Ooi, B. (2016). 「多次元観測データの高速かつ適応的なインデックス作成」 VLDB Endowment Proceedings 9 ( 14): 1683. doi : 10.14778/3007328.3007334 .
  14. ^エレーラ、スティウ;ダ・シルバ、ラリッサ・ミゲス。レイス、パウロ・リカルド。シルバ、アンダーソン。ポルト、ファビオ（2021）。「SAVIME での疎な時空間データの管理: PH ツリー インデックスの評価」。Anais do XXXVI Simpósio Brasileiro de Bancos de Dados : 337– 342. doi : 10.5753/sbbd.2021.17895。S2CID 245185935。 
「 https://en.wikipedia.org/w/index.php?title=PH-tree&oldid=1328234011」から取得