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

DOI 情報処理学会

書誌事項

タイトル別名
  • An approximate Range Search Algorithm with a Graph-based Index on High-dimensional data

この論文をさがす

抄録

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

Range search is a primitive operator in databases, information retrieval, information recommendation, and data mining. Recently, many applications have been generating high dimensional data. Although they require fast similarity search in any metric space, exact and efficient range search on high-dimensional data is difficult and existing tree-based indices suffer from the curse of dimensionality. Dimensionality reduction based algorithms have been proposed, but they are not available on metric space. Proximity graph-based indices have recently shown superior performances on high-dimensional data w.r.t both efficiency and accuracy. In this paper, we extend a state-of-the-art graph-based index, which can be built only on the Euclidean space, so that we can utilize it on any metric space. Furthermore, we propose a novel approximate range search algorithm with a graph-based index. Our experiments on real datasets confirm that our algorithm provides a significantly better efficiency compared with state-of-the-art while keeping almost perfect results.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ