- 著者
-
武藤 大志
多田 匡志
岩村 雅一
黄瀬 浩一
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. CQ, コミュニケーションクオリティ (ISSN:09135685)
- 巻号頁・発行日
- vol.109, no.373, pp.109-114, 2010-01-14
近似最近傍探索は,クエリと最も距離が近い点を探索する最近傍探索の計算時間,メモリ使用量を大幅に削減する手法である.一般に精度,計算時間,メモリ使用量はトレードオフの関係にあり,その関係を解析することは,様々な場面に近似最近傍探索を適用する上で,重要な課題である.本稿では,ハッシュを利用した近似最近傍探索において,文献[1]〜[4]で行われている"隣接バケットを参照する"方策のモデル化を行い,精度とメモリ使用量に関して理論式を求める.そして,実験とシミュレーションにより理論式の妥当性を検証する.