クエリの偏りを利用した学習型最近傍探索問題とその一解法

• Item type: SIG Technical Reports(1)
• 公開日: 2016-08-29
• タイトル: クエリの偏りを利用した学習型最近傍探索問題とその一解法
• タイトル / 言語: en
• タイトル: Trainable nearest neighbor search exploiting query bias
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学
• 著者所属: 和歌山大学
• 著者所属(英): en
• 著者所属(英): Wakayama University
• 著者所属(英): en
• 著者所属(英): Wakayama University
• 著者名: 香川, 椋平; 和田, 俊和
• 著者名(英): Ryohei, Kagawa; Toshikazu, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最近傍探索は，類似画像検索や，BoF 特徴ベクトルの生成，画像間の特徴の対応付けなど，多岐にわたって用いられている．手法としては Hash 型，木探索型，森探索，グラフ探索，など様々な手法があり，問題としては，1- 最近傍探索，k- 最近傍探索，Radius 探索，などがある．近年では格納データの分布の次元が上昇することによって探索速度が低下するという問題を回避するために，近似最近傍探索がよく使われている．これに対し，本稿では，クエリ側の分布を利用した検索の高速化問題を提案する．これを 「学習型最近傍探索問題」 と呼ぶことにする．この分布は逐次与えられるクエリ自身から学習することもできるため，近似最近傍探索と近似のない最近傍探索を並列動作させればオンライン学習もできる．本稿では，その一歩として，クエリに基づいて k-d tree を再構築し，木探索のみで最近傍探索を行う高速化手法を提案する．学習した k-d tree を用いた最近傍探索時間と精度の比較を行い，その活用法を論じる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Nearest neighbor search is widely used in many applications, such as, similar image search, BoF vector construction, keypoint matching between two images, and so on. Nearest neighbor search problem includes three major sub-problems, 1-nearest neighbor search, k- nearest neighbor search, and radius search. Also, the problem can be classified into two problems depending on their accuracy, approximate and accurate search problems. The algorithms can be classified depending on the data structures used for indexing; table, tree, forest, and graph. These well organized classification and criteria imply that this research field is well matured. In this report, however, we further propose a new problem in this field for accelerating the search speed exploiting the query vector distribution. We call this "training problem of nearest neighbor search". This problem is to accelerate the nearest neighbor search by providing query vector distribution. One solution for solving problem is to run both accurate nearest neighbor search and trainable approximate search. That is, if their answers don't coincide, the approximate search algorithm learns the correct answer by accurate search algorithm. By iterating this process, the approximate search gradually approaches to the accurate search while keeping the speed. This report examines one example of this framework based on k-d tree algorithm and confirmed the effectiveness.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11131797
• 書誌情報: 研究報告コンピュータビジョンとイメージメディア（CVIM）; 巻 2016-CVIM-203, 号 24, p. 1-6, 発行日 2016-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8701
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会