楕円体問合せのための空間変換を用いた類似探索アルゴリズム

櫻井 保志  吉川 正俊  植村 俊亮  片岡 良治  

誌名
電子情報通信学会論文誌 D   Vol.J85-D1   No.3   pp.303-312
発行日: 2002/03/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: データベース
キーワード: 
類似探索,  高次元空間,  楕円体問合せ,  空間変換法,  空間索引,  

本文: PDF(485KB)
>>論文を購入


あらまし: 
類似検索メカニズムはユークリッド距離関数のみならず,より一般的な楕円体距離関数を扱える能力をもつことが望ましい.本論文では,楕円体問合せのための探索手法である空間変換法(STT; Spatial Transformation Technique)について述べる.提案手法は空間変換の概念に基づいており,楕円体距離関数に基づく問合せを効率的に支援することができる.これまでにも,多次元索引構造を用いて楕円体問合せを処理する手法が提案されているが,これらの手法は問合せ点と包囲方形との距離の計算に多くの時間を必要とし,ディスクアクセスコストよりも高いCPUコストが生じる.提案手法の基本的なアイデアは,問合せ点からの距離を楕円体距離関数で計算しなければならないようなもとの空間に位置する包囲方形を,ユークリッド距離空間中のオブジェクトに変換することである.もとの空間の包囲方形を新たな空間に変換すると多次元多角形に変化するが,多次元空間における多次元多角形と問合せ点との距離計算には多くのCPU時間が必要となる.そこで,多次元多角形を用いる代わりに,その多次元多角形に外接する方形を距離計算に用いる.このことにより,STTはフォルスドロップを生み出さないことを保証する.従来手法と比較して,提案手法は空間変換による距離近似によってCPUコストの低減化を達成している.評価実験では様々な問合せ行列を用い,提案手法の有用性を示した.