Publications

カンファレンス (国内) 近接グラフを用いたメトリック空間における効率的な近似範囲検索アルゴリズム

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

第12回データ工学と情報マネジメントに関するフォーラム (DEIM 2020)

2020.3.2

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

Paper : 近接グラフを用いたメトリック空間における効率的な近似範囲検索アルゴリズム (外部サイト)