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

• Item type: Journal(1)
• 公開日: 2021-04-15
• タイトル: 高次元データに対するグラフインデックスを用いた近似範囲検索アルゴリズム
• タイトル / 言語: en
• タイトル: An approximate Range Search Algorithm with a Graph-based Index on High-dimensional data
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] グラフインデックス，範囲検索
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• ID登録: 10.20729/00210561
• ID登録 / ID登録タイプ: JaLC
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科／JSTさきがけ
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: ヤフー株式会社
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University / JST PRESTO
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Yahoo Japan Corporation
• 著者名: 新井, 悠介; 天方, 大地; 原, 隆浩; 藤田, 澄男
• 著者名(英): Yusuke, Arai; Daichi, Amagata; Takahiro, Hara; Sumio, Fujita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 範囲検索は，データベース，情報検索，情報推薦，およびデータマイニングなど，幅広い分野で応用されており，その高速化は重要な課題である．また，近年では画像および音声をはじめとする高次元データを扱うアプリケーションが増えている．しかし高次元データの範囲検索は，次元の呪いにより，木構造を用いた従来手法では高速化が困難である．また，高次元データを低次元空間に写像する近似手法では，利用する距離関数によっては写像の設計が困難である．近年，次元削減を行わないデータ構造として，グラフを用いたインデックスが注目されている．本論文では，ユークリッド空間におけるグラフを用いたインデックスをメトリック空間に拡張し，任意の距離関数の利用を可能にする．さらに，グラフを用いた効率的な近似範囲検索アルゴリズムを提案する．実データを用いた実験により，提案アルゴリズムの有効性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 62, 号 4, p. 1086-1098, 発行日 2021-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764