Japanese / English

文献の詳細

論文の言語 日本語
著者 武藤 大志,多田 匡志,岩村 雅一,黄瀬 浩一
論文名 ハッシュを利用した近似最近傍探索における隣接バケット参照の精度とメモリ使用量の理論式の導出
論文誌名 電子情報通信学会技術研究報告
Vol. 109
No. 374
発表番号 PRMU2009-170
ページ pp.109-114
年月 2010年1月
要約 近似最近傍探索は,クエリと最も距離が近い点を探索する最近傍探索の 計算時間,メモリ使用量を大幅に削減する手法である. 一般に精度,計算時間,メモリ使用量はトレードオフの関係にあり, その関係を解析することは,様々な場面に近似最近傍探索を適用する上で, 重要な課題である. 本稿では,ハッシュを利用した近似最近傍探索において, 文献~\cite{nog,PCH,M-P_LSH,mvh}で行われている“隣接バケットを参照する” 方策のモデル化を行い, 精度とメモリ使用量に関して理論式を求める. そして,実験とシミュレーションにより理論式の妥当性を検証する.
一覧に戻る