複数の非類似度を自由に重みづけできる単一のグラフ索引を用いた最近傍探索手法

• Item type: Symposium(1)
• 公開日: 2015-11-17
• タイトル: 複数の非類似度を自由に重みづけできる単一のグラフ索引を用いた最近傍探索手法
• タイトル / 言語: en
• タイトル: Nearest neighbor search method under variably-weighted multiple dissimilarities using a single graph index
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 奈良先端科学技術大学院大学
• 著者所属: NTTサービスエボリューション研究所
• 著者所属: NTTコミュニケーション科学基礎研究所
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): NTT Service Evolution Laboratories
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories
• 著者名: 田村, 真一; 澤田, 宏; 山田, 武士
• 著者名(英): Shinichi, Tamura; Hiroshi, Sawada; Takeshi, Yamada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，探索ごとに複数の非類似度の重みづけを自由に変えて探索できる，単一の索引を用いた最近傍探索手法を提案する． 多くの最近傍探索問題において非類似度の基準は一つとは言えず，それらの中でどの非類似度をどの程度重視するかを探索のたびに設定できる手法が求められている． これまでに提案されている手法で複数の非類似度を取り扱うには，事前に重みづけを固定するか，それぞれの非類似度での結果を統合する方法がとられることが多かった． しかし事前に重みを固定する手法では探索時に重みを調整することは難しく，また結果統合の手法ではそれぞれの基準では中位に来るが重みづけた基準では上位に来るような結果が出力されにくい． 本研究では，複数の非類似度に対する任意の結合重みを考慮した単一のグラフを索引に用いることで，探索時にはその結合重みを自由に設定できる最近傍探索手法を提案する． 実画像データセットを使ったさまざまな重みづけに対する実験の結果，提案手法は索引を 1 回しか構築しないにもかかわらず，それぞれの重みで固定して作った従来の索引構造に匹敵する探索コストと精度を達成することができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper introduces the nearest neighbor search method using a single index, which allows users to put weights on the multiple dissimilarities for each search trial. Many of nearest neighbor search problems come up with more than one dissimilarity, which are desired to be weighted on-the-fly. To cope with this sort of multiple dissimilarities using existing search methods, we usually fix the weights beforehand or aggregate results from each dissimilarity afterward. However, pre-fixed weights are not adjustable on the search stage, and result aggregation methods are unlikely to give a result which would be top-ranked on the weighted dissimilarity while middle on each of the unweighted dissimilarities. We propose the novel nearest neighbor search method which allows users to set combination weight of multiple dissimilarities at the search stage, by using a single graph index constructed taking arbitrary weights into consideration. In the experiment with the real image dataset and variable weights, our index performs comparably to the conventional indices which is constructed with pre-fixed weights although our index is constructed only once.
• 書誌情報: 第8回Webとデータベースに関するフォーラム論文集; 巻 2015, p. 182-189, 発行日 2015-11-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会