著者

片山 紀生 佐藤 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.80, no.8, pp.703-717, 1997-08-25

被引用文献数

38

---

画像データに対する内容検索の実現法として, 特徴ベクトルを類似検索する方法が広く使われており, その高速化のためのインデックス構造が求められている. これまでにR^*-treeを用いる方法や, 新たに考案されたSS-treeを用いる方法が提案されているが, 本研究では, これらのインデックスよりも更に高速なインデックスとしてSR-tree (Sphere/Rectangle-Tree)を提案する. SR-treeの特徴は, 包囲球(bounding sphere)と包囲長方形(bounding rectangle)を併用する点にある. これまでにも, 包囲球はSS-treeで, 包囲長方形はR^*-treeで使われている. しかし, 本研究が行った実験によると, 次元が高くなった場合, 包囲長方形を用いる方法では1辺の長さと対角線の長さの差が大きくなるという問題があり, 包囲球を用いる方法では包囲長方形よりも体積が大きくなるという問題があることがわかった. そこで, SR-treeではこれらを同時に使用することによって, 高次元空間をR^*-treeやSS-treeよりもより効果的に分割することを可能にする. 評価実験を行った結果, CPU時間, ディスクアクセス回数, いずれの面についても, SR-treeがR^*-treeならびにSS-treeを上回ることが確認された.