Sort-Tile-Recursive (STR) algorithmの論文についてまとめてみる

これは何?

Sort-Tile-Recursive (STR) algorithm に関して日本語・英語で説明された記事がなかった (+英語で書かれたスライドが間違っていた) ため, 原論文を読んでまとめることとした.

Sort-Tile-Recursive (STR) とは?

R-treeと共に用いられるpacking algorithmの一種である.

以下の論文で提案されている.

Leutenegger, Scott and A. Lopez, Mario and Edgington, Jeffrey, STR: A Simple and Efficient Algorithm for R-Tree Packing, 1997. .

何に使うの?

幾何データを管理するインデックスとして使われている.

例えばGoogleのGeofencingシステムでは, 空間インデックスとしてSTR-treeが利用されている. これは幾何計算ライブラリJTS Topology Suiteに実装されているものを利用している.

developers.googleblog.com

R-treeとは?

R木 - Wikipedia

木構造の一種である. 主に多次元データ(平面図形, 位置座標, 立体図形等)を管理するのに用いられる.

例えば以下の図は, R1からR19までの長方形データを管理するR-treeの例である. 複数の矩形をまとめて新たな長方形 (=ノード) とすることで, 空間クエリによる問い合わせを効率よく処理する. ここでいう「効率のよさ」とは, 空間クエリに対して無関係な長方形がヒットしないことを指す.

二次元データにおけるR-tree (Wikipedia)

packing algorithmとは?

packing algorithm: 複数あるデータをまとめる (=packingする) アルゴリズムである.

論文中では特に, R-treeに合わせて用いるpacking algorithmとしてNearest-X (NX), Hilbert Sort (HS), Sort-Tile-Recursive (STR)の三種類を比較して評価している.

三種類に共通する処理

R-tree構築の処理フローを述べる.

定義

r: 長方形データ数

b: R-treeのノードが保有できる最大要素数

Minimum Bounding Rectangle (MBR): その図形を囲う最小外接矩形

ページ番号: グループの識別子

図形とMinimum Bounding Rectangle (MBR)

処理フロー

1. r個の長方形データをceil(r/b)個のグループb個にpackingする.

2. 各グループのMBRとページ番号を出力する. ページ番号は子ポインタとして, 次のより高いレベル(=浅い深さ)のノードで利用される.

3. これらのMBRを再帰的にpackingして, 次の高いレベルのノードにする. rootノードが作られるまで行う.

最初にpackingすることで, 各グループは要素数がbで, 最後のグループはb以下の要素数となる. これらのグループはすべて同じ葉レベル (=根から同じ深さ)になる.

例えば下図のようにr=13, b=6とする. この時 ceil(13/6) = 3であるので, グループは6,6,1で分けられる.

packing, 高いレベルのノード生成

長方形を何らかのpacking algorithmでpackingして高レベルのノードを作る, といった処理を再帰的に実施する.

本稿ではNXとHSについては触れず, STRを対象とする.

STRによるpacking

多次元に拡張できるアルゴリズムであるが, 本稿では2次元についてのみ対象とする.

定義

r: 長方形データ数

b: R-treeのノードが保有できる最大要素数

P: グループ数

S: スライス数

前提

r個の超長方形で構成されるk次元のデータファイルを考える.

超長方形: 各k次元は区間 [Ai, Bi] (1<=i<=k) 内に存在する (例. k=2であれば長方形が最大b個存在)

k=1の時

B-treeと同じ

k=2の時

2次元平面上で空間をいくつかにスライス(=分割)することを考える. スライスされた部分空間をtileと呼ぶ.

P = ceil(r/b), S = ceil(sqrt(P))とする.

1. r個の長方形について, それぞれの中心点(x, y)を計算する.

2. 中心点のx座標で全長方形をソートし, S本の縦線でスライスする.

3. 中心点のy座標で各slice内の長方形をソートし, b個ずつpackingしてノードとする.

手順1

手順2

手順2では, R2のx座標 < R1のx座標であるため順序を入れ替えている.

手順3

手順3では, y座標で昇順ソートした後に高いレベルのノードを生成する.

sliceされる際, 個々のtileは計Sb個の長方形を含む. 最後のtileはSb以下の長方形を含む.

k>2の時

k=2を一般化することができる. 内容省略.

STRで何が嬉しいの?

定性的

x軸とy軸でソートを繰り返すため, 各長方形が可能な限り正方形上に近い形でpackingされる.

STRによるpacking

HSによるpacking

NXによるpacking

定量的

空間クエリの問い合わせに対するディスクアクセス回数が減少 (HS, NXと比べて)

ディスクアクセス回数が少ない->クエリに不要なデータを検索していない->効率がよい, というロジックである.

しかしながら, 図形・クエリサイズによってはHSに負けてしまうこともある. 特にCFDデータセットを用いた場合はHSに負けている.

まとめ

論文に謎の変数nが誤植されていたり, 唯一存在した解説スライド(英語)が間違っていたりと色々ありましたが, 実際に論文のほう読んで理解できたので良かったです.

冒頭でも述べましたが, JTS Topology Suiteで実装されているほど有名な空間インデックスなので, 空間クエリの種類や管理するデータの特性によってはお世話になるかと思います.

時間があればHSも調べてみたいです. おわり.