仮想包囲矩形に基づく多次元データ集合に対する近傍探索

概要

論文の詳細を見る
本論文では, 多次元空間内のオブジェクト近傍探索に有用な新たな索引構築手法を提案する. 多次元空間探索における代表的な手法として, R-treeとその派生手法など, 空間探索を高速化するためにMBR(最小包囲矩形)や包囲球を用いて木構造を構築し, 索引生成を行う手法がある. これに対し本論文では, MBRを用いた木構造を利用するとともに, 新たにVBR(仮想包囲矩形)の概念を導入する. VBRはMBRを包含し, かつ近似する矩形である. また, 本論文ではVBRに基づいた新手法である部分空間符号化法を提案する. これは木構造において親ノードのVBRの内部に, 相対的位置を用いたVBRを低コストで表現するものである. VBRおよび部分空間符号化法の概念はMBRを用いた空間索引の種類とは直交する. すなわち, R-tree, R^*-tree, X-treeなどのMBRを用いた空間索引にVBRおよび部分空間符号化法の概念を導入し, それを用いる探索, 更新アルゴリズムを構築できる. 本論文では実際にVBRをR^*-treeに適用し, 実装した探索と更新アルゴリズムを用いて評価実験を行った結果を与える. 多次元データ集合を用いたR^*-treeとの比較では, 蓄積コストは1%程度上昇するものの, 一様分布データでは約12%, 実データでは約14%の探索性能向上が可能となり, 本手法の優位性が明らかとなった.
一般社団法人情報処理学会の論文
1999-02-15

仮想包囲矩形に基づく多次元データ集合に対する近傍探索

スポンサーリンク

概要

著者

関連論文

スポンサーリンク