近年、データベースマネージメントシステム（DBMS）への要求のひとつとして空 間データを扱う能力への期待が高まってきており、実際に多くのアプリケーショ ンで空間データが使用されている。これらのアプリケーションで使用されている 問い合わせとして最も代表的なものに、矩形を指定することでそこに交差するノー ドを検索するrange queryと呼ばれるものがある。このrange queryをサポートす る効率的なデータ構造としてR-treeが存在する。
本論文ではこのR-treeに焦点を合わせ、既存のR-treeの性能を上回る新たな R-tree構造であるHilbert R-treeを提案する。 R-treeのより優れた構造を考える際には、より優れたノードの順序付けを行うこ とで最小包囲矩形（MBR）の領域が最小となるようなノード分割を行うことが重 要になる。 Hilbert R-treeでは"2D-c"と呼ばれる、矩形の中心のHilbert値に応じて矩形を ソートし順序付けを行うという手法を使用している。この方法を用いた順序付け を行うことで全てのノードが同胞ノードの集合をもち、ノードの分割が行われる。 このHilbert R-treeについて、アルゴリズムを詳細に設計した上で実装を行った。
本発表では、R-treeの基本的な性質について触れた上で、実装したHilbert R-treeの詳細な構造、ノードの挿入、削除などの操作アルゴリズムについて述べ る。また、実験としてR-tree構造の中でもっとも検索効率の良いものとされる R*-treeとのrange queryを用いた検索性能の比較を行うことで、Hilbert R-tree の優位性を示す。
キーワード：R-tree,R*-tree,空間データモデル,空間問合せ処理,Hilbert曲線
CADや地図データを使うアプリケーションにおいて、データベースの空間データ を効率的に取り扱うためにインデックスが必要となる。このインデックスは空間 的位置に従い高速に検索ができなければならない。空間アクセス手法（spatial access method: SAM）は複雑な空間オブジェクトをデータ空間の軸に平行な矩形 （minimum bounding rectangle）により近似することに基づいている。この簡単 な近似での最も重要な特徴は複雑なオブジェクトを少ないデータ量で表現できる ことにある。多くの情報は失われるが、空間オブジェクトの最小包囲矩形はオブ ジェクトの最も重要な幾何学的性質を保持している。 有名な空間アクセス手法であるR-treeはB+-treeに基づいており、それぞれのノー ド内にある閉じた矩形の領域を発見的手法で最適化する。最適化の基準はそれぞ れの包囲矩形の領域を最小にすることにある。しかし、この手法は検索効率を低 下させる矩形同士の重なりを最小にすることができない。R-treeの別形である R*-treeはあるノード内にある包囲矩形の領域、矩形の辺長、重なりの組み合わ せを最適化することができる。さらに、点と空間データを同時にかつ効果的にサ ポートし、実装コストは他のR-treeに比べ少し高いだけである。本論文では実験 により他の別形R-treeであるGuttmanのlinear 、quadratic R-treeやGreeneの R-treeと比較してもR*-treeはすべての面で性能が高いことを示している。
キーワード：R*-tree、R-tree、空間アクセス手法、動的索引構造
動画データを検索したり編集する場合には,目的の場面を見つけるために動画デ ータへの効率的なアクセス法が必要となる.動画を順序を持つ連続したフレーム として見ると,それぞれのフレームは,そのフレーム中に現れるオブジェクトが占 有する2次元空間からなる.動画はこのような表現ができるので,連続したフレー ムを1つの次元として捉え,動画オブジェクトを3次元空間中のオブジェクトとす ることが可能である.これを3次元のインデックス(R-treeやその変形)を用いてイ ンデックシングする方法が動画データへの効率的なアクセス法を与える簡単な方 法である.しかしこの場合連続したフレームに続けて出現するオブジェクトは,連 続したフレームを表す軸において長い範囲が割り当てられてしまう.ある1つの軸 において,他の軸と比較して長い範囲を占有するオブジェクトを3次元のインデッ クスを用いて効率的にクラスタリングすることは困難であり,このことは検索性 能に悪影響を与える.
そこで,本論文ではこの問題を解決する動画オブジェクトの新しいインデックシ ング法を提案している.新しいインデックシング法とは, partial- persistence を利用したインデックスである.データが persistence であるとは,データがそ れぞれバージョンを持ち,データが変更された場合,以前のバージョンのデータは そのまま保持し,新しいバージョンのデータが追加されるというようなデータで ある.つまり全てのバージョンのデータを更新でき,アクセスできる.データが partial- persistence であるとは,全てのパージョンのデータにアクセスできる が,更新できるデータは最も新しいバージョンのみであるようなデータである.本 論文では,連続したフレーム中におけるオブジェクトを2次元のインデックスと partial- persistence を利用してインデックシングする方法を提案している.
また,本論文では,動画オブジェクトは一連のフレーム中で,移動したり,領域が 拡大,縮小するものであるとしている.そのためにこのようなオブジェクトを効率 的にインデックシングするためにオブジェクトの変化を近似する方法を提案して いる.
キーワード : アクセス法, 時空間データベース, 動画オブジェクト, マルチメディア
コンテンツベースの画像検索においては、特徴ベクトル上での 類似検索が広く使われてきた。この手法を大規模データベース に適用するには、多次元インデックス構造を、最近接探索(Nea rest Neighbor Query)を効率的に扱えるように発展させる必要 がある。このため、SS-treeが提案され、これはR*-treeやK-D- B-treeのような他のインデックス構造よりも良い性能を示すこ とが知られている。SS-treeの最も重要な特徴は、領域を扱うの に包囲矩形ではなく、包囲球を用いることである。しかし、包 囲球は高次元のデータにおいては、包囲矩形よりも多くの体積を 占め、その結果、検索の効率を落とすことになる。この欠点を克 服するために、本論文では、包囲矩形と包囲球を統合したSR-tree (Sphere/Rectangle-tree)と呼ばれる新しいインデックス構造が 提案されている。SR-treeにおける領域は包囲矩形と包囲球の交 差により決定される。包囲矩形を組み合わせることにより、探索 空間をSS-treeの場合より小さな領域へと分割することが可能と なり、領域間の分散性を改良している。これにより、特に画像、 ビデオの類似画像検索のためのインデックスにおいて実際的であ る高次元かつ一様でないデータに対する最近接探索の性能を高め ることができる。本論文では、SR-treeの利点を保証する性能テス ト結果を含め、SR-treeがSS-treeやR*-Treeよりも高性能である ことが示されている。
キーワード：類似検索、多次元インデックス、最近接探索
お断り：
このページは，牧之内顕文研究室が行なった最新のデータベース研究についての論文紹介
についてまとめています．
このページは，研究室内部での情報交換と，研究室活動についての情報公開に
あります．
記載の内容について，誤りなどがあれば，論文紹介を行なった我々に責任があります．