著者

武藤 大志 多田 匡志 岩村 雅一 黄瀬 浩一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CQ, コミュニケーションクオリティ (ISSN:09135685)

巻号頁・発行日

vol.109, no.373, pp.109-114, 2010-01-14

---

近似最近傍探索は,クエリと最も距離が近い点を探索する最近傍探索の計算時間,メモリ使用量を大幅に削減する手法である.一般に精度,計算時間,メモリ使用量はトレードオフの関係にあり,その関係を解析することは,様々な場面に近似最近傍探索を適用する上で,重要な課題である.本稿では,ハッシュを利用した近似最近傍探索において,文献[1]〜[4]で行われている"隣接バケットを参照する"方策のモデル化を行い,精度とメモリ使用量に関して理論式を求める.そして,実験とシミュレーションにより理論式の妥当性を検証する.