Publications

JOURNAL (DOMESTIC) 高次元データに対するグラフインデックスを用いた近似範囲検索アルゴリズム

新井 悠介 (阪大), 天方 大地 (阪大), 原 隆浩 (阪大), 藤田 澄男

情報処理学会 論文誌ジャーナル (情報処理学会論文誌)

April 15, 2021

範囲検索は,データベース,情報検索,情報推薦,およびデータマイニングなど,幅広い分野で応用 されており,その高速化は重要な課題である.また,近年では画像や音声をはじめとする高次元データを 扱うアプリケーションが増えている.しかし高次元データの範囲検索は,次元の呪いにより,木構造を用 いた従来手法では高速化が困難である.また,高次元データを低次元空間に写像する近似手法では,利用 する距離関数によっては写像の設計が困難である.近年,次元削減を行わないデータ構造として,グラフ を用いたインデックスが注目されている.本稿では,ユークリッド空間におけるグラフを用いたインデッ クスをメトリック空間に拡張し,任意の距離関数の利用を可能にする.さらに,グラフを用いた効率的な 近似範囲検索アルゴリズムを提案する.実データを用いた実験により,提案アルゴリズムの有効性を示す.

Paper : 高次元データに対するグラフインデックスを用いた近似範囲検索アルゴリズム (external link)