空間分割と直交変換の統合による高次元最近傍探索の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2006-03-16
• タイトル: 空間分割と直交変換の統合による高次元最近傍探索の高速化
• タイトル / 言語: en
• タイトル: Nearest Neighbor Search in High-Dimensional Space based on Space Decomposition and Orthogonal Basis Selection
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学システム工学部システム工学研究科
• 著者所属: 和歌山大学システム工学部システム工学研究科
• 著者所属: 和歌山大学システム工学部システム工学研究科
• 著者所属(英): en
• 著者所属(英): Department of Computer and Communication Science Wakayama University
• 著者所属(英): en
• 著者所属(英): Department of Computer and Communication Science Wakayama University
• 著者所属(英): en
• 著者所属(英): Department of Computer and Communication Science Wakayama University
• 著者名: 荒井, 英剛; 加藤丈和; 和田, 俊和
• 著者名(英): Hidetaka, Arai; Takekazu, Kato; Toshikazu, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 事例に基づく学習や認識において，最近傍探索技術は重要な基礎技術として位置づけられる．従来，最近傍探索の高速化技術として様々な手法が提案されているが，これらのほとんどの手法は最近傍候補の絞り込みによる手法である．しかし，30 次元を超える高次元空間ではこれらの手法はほとんど全探索となり，画像を直接扱うような，数千から数万次元で有効な最近傍探索の高速化手法は提案されていない．本研究では，K-D Tree やANNで採用されている空間分割に基づく絞り込み手法に，主成分分析による直交変換を統合することで，高次元でも有効な最近傍探索の高速化手法を提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Nearest Neighbor (NN) search is essential for case/instance based reasoning. Most NN search methods proposed so far are based on NN candidate narrowing and these methods degenerates to brute force search in high-dimensional space over 30D. Efficient NN search algorithm dealing with image database in over thousand dimensional space has not been proposed. In this paper, we propose an effective NN search algorithm integrating orthogonal expansion by PCA and space decomposition, which works in very high dimensional space. This method can be regarded as a natural extension of ANN. Through extensive experiments, we confirmed the efficiency of our method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11131797
• 書誌情報: 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）; 巻 2006, 号 25(2006-CVIM-153), p. 41-48, 発行日 2006-03-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会