- @ThothChildren
- 2018.10.28
- PV 164
ヒルベルトR-Tree
ー 概要 ー
ヒルベルトR-Treeは空間充填曲線であるヒルベルト曲線を用いてデータを順序づけしてより高速に効率的なデータ構造を作って高速化したR-Tree.ヒルベルト曲線は多次元を近いものを近いまま1次元に落とし込む曲線で今回の最小外接矩形の作成に寄与する.
この章を学ぶ前に必要な知識
条件
- 矩形情報や立方体情報などのデータが入力
効果
- 空間での探索に特化しており多次元データを高速に探索するデータ構造
- B-Treeを多次元にしたR-Treeを工夫して高速化したヒルベルトR-Tree
ポイント
- 更新、削除、追加がほぼないならPacked hilbert R-tree
- 更新、削除、追加が多いならDynamic Hilbert R-Tree
- 如何に最小外接矩形をクラスタリングするかがR-Treeの効率化には大切でそれを工夫している
- 空間充填曲線であるヒルベルト曲線は、高次元で近いものに一次元の近いインデックスを割り当てることができる
解 説
この章を学んで新たに学べる
Comments
Reasons
知識: ヒルベルト曲線
ヒルベルト曲線(Hilbert Curve)は、平面や空間内の単位正方形、単位立方体を特定のパターンに乗っ取って全て通るフラクタルな空間補充曲線の一つ.(一本の線で全部のブロックを通るようにする)他の空間充填曲線によってマッピングを行うよりもより位置関係を保持する曲線になっている.応用例も多く、空間インデックスや検索、などがある.1次元の値がn次元に対応しているため、原点からの距離が近いとその空間でも近いとわかる.
知識: R-Tree
R-Treeは空間インデックスなどに使用される空間データや矩形情報などの多次元データを扱うツリー型データ構造.矩形データを近いもので集めてそれらの最小外接矩形を親ノードとしてつなげていく.