Japanese / English

文献の詳細

論文の言語 日本語
著者 佐藤 智一, 岩村 雅一, 黄瀬 浩一
論文名 概算距離の精度向上による近似最近傍探索の高速化
論文誌名 電子情報通信学会技術研究報告
Vol. 111
No. 193
発表番号 PRMU2011-67
ページ pp.61-66
発表場所 北海道函館市
査読の有無
発表の種類 口頭発表
年月 2011年9月
要約 登録されたデータからクエリに最も近いものを探し出す最近傍探索問題では, 探索誤りを許容することで計算時間を大幅に削減することができ,これを近似 最近傍探索問題と呼ぶ. 近似最近傍探索は一般に, 最近傍点となる確率の高い点を選択し, それらとクエリとの距離を計算するという 2段階の処理で実現され,前者が手法の良し悪しを決定する. 本稿では,この処理で用いる「概算距離」を計算量を増やすことなく, より高精度に推定することにより, 高精度かつ高速な近似最近傍探索,を実現する手法を提案する. 実験の結果, $50\%$の精度で比較すると従来手法[1]と比べて,64次元のデータで約4倍,256次元のデータで約2.5倍の処理速度を得ることが確認できた.
一覧に戻る