Bxツリー

コンピュータサイエンスのクエリ

コンピュータ サイエンスにおいて、B ^xツリーは、移動するオブジェクトの効率的なB+ ツリーベースのインデックス構造を更新するために使用されるクエリです。

インデックス構造

B ^xツリーの基本構造はB+ツリーであり、内部ノードはディレクトリとして機能し、各ノードは右兄弟へのポインタを保持しています。以前のバージョンのB ^xツリーでは、^[1]リーフノードには、インデックス付けされる移動物体の位置と対応するインデックス時刻が含まれていました。最適化されたバージョンでは、^{[2]各リーフノードエントリには、オブジェクトのID、速度、1次元マッピング値、および最新の更新時刻が含まれています。移動物体の位置は}マッピング値から導出できるため、位置を保存しないことでファンアウトが増加します。

移動オブジェクトにB+ツリーを活用する

^{最大更新間隔tmu内でインデックスパーティション数が2であるB x}ツリーの例。この例では、最大3つのパーティションが同時に存在します。線形化後、時刻0に挿入されたオブジェクトの位置は、ラベルタイムスタンプ0.5 tmuでパーティション0にインデックス付けされ、時刻0から0.5 tmuの間に更新されたオブジェクトの位置は、ラベルタイムスタンプtmuでパーティション1にインデックス付けされ、以下同様に続きます（矢印で示されています）。時間の経過に伴い、最初の範囲の有効期限が切れ（網掛け部分）、新しい範囲が追加されます（破線）。

他の多くの移動物体インデックスと同様に、2次元の移動物体はO = ((x, y), (vx, vy), t ) という線形関数としてモデル化されます。ここで、(x, y) と (vx, vy) は、特定の時間インスタンスt 、つまり最後の更新時間における物体の位置と速度です。 B+ ツリーは、1次元データのインデックス構造です。 B+ ツリーを移動物体インデックスとして採用するために、 B ^{xツリーは、時刻}tにおける物体の位置を1次元の値に統合するのに役立つ線形化手法を使用します。具体的には、まずオブジェクトは更新時間に従って分割されます。同じパーティション内のオブジェクトの場合、 B ^{xツリーは、}線形補間によって推定された特定の時間における物体の位置を格納します。そうすることで、 B ^xツリーは、各オブジェクトの更新時間を格納せずに、同じパーティション内のすべてのオブジェクトの一貫したビューを維持します。

次に、空間はグリッドによって分割され、オブジェクトの位置は、ペアノ曲線やヒルベルト曲線などの空間充填曲線に従ってパーティション内で線形化されます。

最後に、パーティション番号 (時間情報) と線形順序 (位置情報) を組み合わせて、オブジェクトは1 次元のインデックス キー B ^x値 を使用して B ^{xツリーにインデックス付けされます。}

${\displaystyle B^{x}{\text{ value}}\left(O,t\right)=\left[{\text{index partition}}\right]_{2}+\left[{\text{xrep}}\right]_{2}}$

ここで、index-partition は更新時間によって決定されるインデックス パーティションであり、xrep はインデックス付けされた時間におけるオブジェクト位置の空間充填曲線値であり、x のバイナリ値を示し、「+」は連結を意味します。 ${\displaystyle \left[X\right]_{2}}$

オブジェクトO((7, 2), (-0.1,0.05), 10)、tmu = 120の場合、OのB ^x値は次のように計算できます。

1. 前述の通り、Oはパーティション0にインデックス付けされています。したがって、indexpartition = (00) _{2 となります}。
2. パーティション0のラベルタイムスタンプにおけるOの位置は(1,5)です。
3. 次数3のZ曲線を使用すると、OのZ値、つまりxrepは(010011) _2になります。
4. indexpartitionとxrepを連結すると、B ^x value (00010011) ₂ =19になります。
5. 例 O ((0,6), (0.2, -0.3 ),10) かつ tmu=120 の場合、パーティションのラベルタイムスタンプにおける O の位置は次のようになります: ???

挿入、更新、削除

新しいオブジェクトが与えられると、そのインデックスキーが計算され、B+ツリーと同様に、オブジェクトがB ^xツリーに挿入されます。更新は、削除とそれに続く挿入で構成されます。各インデックスの最新キーを保持するための補助構造が採用されているため、キーを検索することでオブジェクトを削除できます。インデックスキーは、ツリーに影響を与える前に計算されます。このように、B ^xツリーはB+ツリーの優れた特性を直接継承し、効率的な更新性能を実現します。

クエリ

範囲クエリ

範囲クエリは、現在の時刻より前の時刻に長方形の範囲内にあるすべてのオブジェクトを取得します。 ${\displaystyle q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)}$ ${\displaystyle tq}$

B ^x木はクエリに応答するためにクエリウィンドウ拡大技術を使用します。B ^x木はオブジェクトの位置をその更新時刻以降の時点に格納するため、拡大には2つのケースが考えられます。つまり、位置を以前の時刻に戻すか、後の時刻に進めるかです。基本的な考え方は、ラベルのタイムスタンプ時点ではクエリウィンドウ内に位置していないが、クエリのタイムスタンプ時点ではクエリウィンドウ内に入るすべてのオブジェクトを囲むようにクエリウィンドウを拡大することです。

拡大後、拡大されたクエリウィンドウに含まれるオブジェクトを見つけるために、B ^x木のパーティションを走査する必要があります。各パーティションにおいて、空間充填曲線を用いることで、元の2次元空間における範囲クエリは、変換された1次元空間における範囲クエリの集合になります。^[1]

偏ったデータセット内での拡張後にクエリ領域が過度に大きくなるのを避けるために、クエリアルゴリズムの最適化が存在し、^[3]不要なクエリの拡大を回避することでクエリの効率を向上させます。

K近傍クエリ

k近傍クエリは、k個の回答が得られるまで、段階的に拡大した検索範囲クエリを反復的に実行することで計算されます。別の方法としては、iDistance Techniqueにおける同様のクエリ手法を用いることが挙げられます。

その他の質問

範囲クエリとK近傍クエリアルゴリズムは、間隔クエリや連続クエリなどをサポートするように簡単に拡張できます。^[2]

移動するオブジェクトに対応するためにリレーショナルデータベースエンジンを適応させる

B ^xツリーはB+ツリーインデックス上に構築されたインデックスであるため、挿入、削除、検索など、B ^xツリーのすべての操作はB+ツリーと同じです。これらの操作の実装を変更する必要はありません。唯一の違いは、インデックスキーの導出手順を既存のDBMSのストアドプロシージャとして実装することです。したがって、B ^{xツリーは}カーネルを変更することなく、既存のDBMSに容易に統合できます。

SpADE ^[4]は、オブジェクトのインデックスにB ^x木を使用する、広く普及しているリレーショナルデータベースシステムであるMySQL上に構築された移動オブジェクト管理システムです。実装では、移動オブジェクトデータはMySQLに直接変換・保存され、クエリは標準的なSQL文に変換され、リレーショナルエンジンで効率的に処理されます。最も重要なのは、これらすべてがMySQLコアに侵入することなく、簡潔かつ独立して実現されていることです。

パフォーマンスチューニング

データの偏りによる潜在的な問題

B ^xツリーは、2 次元の位置を 1 次元のキーにマッピングする際に、空間を分割するためのグリッドを使用します。これにより、偏ったデータを処理する際に、クエリと更新操作の両方でパフォーマンスが低下する可能性があります。グリッド セルが大きすぎる場合、セルに多くのオブジェクトが含まれます。セル内のオブジェクトはインデックスと区別できないため、基礎となる B+ ツリーにオーバーフロー ノードが存在することになります。オーバーフロー ページの存在は、ツリーのバランスを崩すだけでなく、更新コストも増加させます。クエリに関しては、特定のクエリ領域に対して、大きなセルは誤検知を増やし、処理時間を増加させます。一方、空間がより細かいグリッド、つまりより小さなセルで分割されている場合、各セルに含まれるオブジェクトは少なくなります。オーバーフロー ページはほとんど存在しないため、更新コストは最小限に抑えられます。クエリで取得される誤検知は少なくなります。ただし、検索するセルの数が増えることになります。検索するセルの数が増えると、クエリのワークロードも増加します。

インデックスチューニング

ST ² B木^[5]は、空間的なデータの偏りや時間的なデータ変化を考慮しながらB ^x木の性能を調整するための自己チューニングフレームワークを導入しています。空間的なデータの偏りに対処するために、ST ² B木は参照点を用いて空間全体をオブジェクト密度の異なる領域に分割します。各領域は個別のグリッドを使用し、そのセルサイズは内部のオブジェクト密度によって決定されます。

B ^xツリーは、異なる時間間隔に関する複数のパーティションを持ちます。時間の経過とともに、各パーティションは交互に拡大および縮小します。ST ² Bツリーは、この機能を利用してインデックスをオンラインでチューニングし、空間のパーティションを調整して、時間によるデータの変化に適応します。特に、パーティションが空になるまで縮小し、拡大し始めると、最新のデータ密度に応じて、新しい参照ポイントのセットと各参照ポイントの新しいグリッドが選択されます。このチューニングは、特定の期間に収集された最新の統計に基づいて行われるため、空間のパーティション分割方法は、最新のデータ分布に最適に適合するはずです。これにより、ST ² Bツリーは、空間内のデータの偏りや時間によるデータの変化による影響を最小限に抑えることが期待されます。

参照

• B+ツリー
• ヒルベルト曲線
• Zオーダー（曲線）

参考文献

1. Christian S. Jensen、Dan Lin、Beng Chin Ooi. 移動オブジェクトの効率的なB+ツリーベースのインデックス作成におけるクエリと更新. 第30回国際超大規模データベース会議（VLDB）の議事録、768-779ページ、2004年。
2. Dan Lin. 移動オブジェクトデータベースのインデックス作成とクエリ、博士論文、シンガポール国立大学、2006年。
3. Jensen, CS, D. Tiesyte, N. Tradisauskas、「移動オブジェクトの堅牢な B+ ツリーベースのインデックス作成」、第 7 回国際モバイルデータ管理会議の議事録、奈良、日本、9 ページ、2006 年 5 月 9 ～ 12 日。
4. SpADE Archived 2009-01-02 at the Wayback Machine : 位置認識サービスのための SPatio-temporal Autonomic Database Engine。
5. Su Chen、Beng Chin Ooi、Kan-Lee. Tan、Mario A. Nacismento、「ST2B-tree：移動オブジェクトのための自己調整可能な時空間B+-tree」、2011年6月11日アーカイブ、Wayback Machine。ACM SIGMOD International Conference on Management of Data (SIGMOD) Proceedings、2008年、29-42ページ。

「https://en.wikipedia.org/w/index.php?title=Bx-tree&oldid=1283258858」から取得