ハッシュを利用した近似最近傍探索における隣接バケット参照の精度とメモリ使用量の理論式の導出

摘要

近似最近傍探索は，クエリと最も距離が近い点を探索する最近傍探索の計算時間，メモリ使用量を大幅に削減する手法である.一般に精度，計算時間，メモリ使用量はトレードオフの関係にあり，その関係を解析することは，様々な場面に近似最近傍探索を適用する上で，重要な課題である.本稿では，ハッシュを利用した近似最近傍探索において，文献［1］～［4］で行われている“隣接バケットを参照する”方策のモデル化を行い，精度とメモリ使用量に関して理論式を求める.そして，実験とシミュレーションにより理論式の妥当性を検証する.%Approximate nearest neighbor search is a technique which greatly reduces processing time and required amount of memory for nearest neighbor search. Generally, there are the relationships of trede-off among accuracy, processing time and memory amount. Thus, analysis on the relationships is an important task for actual use of approximate nearest neighbor search method. In this paper, we construct a model of approximate nearest neighbor search methods with accessing neighboring buckets [1]-[4], and derive theoretical formulae in accuracy and memory amount. We compare simulated values with experimented values.