距離索引VP-treeにおける解絞込みの一改良手法(マルチメディアデータベース,<特集>データ工学論文)

概要

論文の詳細を見る
マルチメディアデータベースでは検索効率を高めるために,多次元空間に基づく索引化法が使用される.しかし,この手法は距離尺度としてユークリッド距離を用いることが前提であるため,汎用性に欠ける.一方,距離公理の成立のみを前提とする距離空間に基づく索引化法は,ユークリッド距離以外の距離尺度も利用できるため,汎用性が高い.本論文では,距離索引の一つであるVP-treeの改良法を提案する.VP-treeは検索時にルートノードから検索範囲に適合するノードをたどり,最終的にたどり着いたリーフノードにリンクされているオブジェクトとの距離を算出し,検索範囲に適合するかを調べる.しかし,リーフノードにおける距離計算が増大すると検索速度が遅くなる.そこで,リーフノードにおける三角不等式を用いた絞込み法に着目し,その改良法として問合せオブジェクトに対する最近傍点を三角不等式の基準点として用いる手法を提案する.この改良により,検索範囲をより小さくし,距離計算回数を削減することが可能になる.実際に10,000件の画像データを用いて評価実験を行った結果,従来手法に比べ検索時間を5〜12%削減することができた.
2008-03-01