Japanese / English

Detail of Publication

Text Language Japanese
Authors Tomoyuki Muto,Masashi Tada,Masakazu Iwamura,Koichi Kise
Title Derivation of Theoretical Formulae of Accuracy and Memory Amount on Accessing Neighboring Buckets in Hash-Based Approximate Nearest Neighbor Search
Journal IEICE Tecnical Report
Vol. 109
No. 374
Presentation number PRMU2009-170
Pages pp.109-114
Month & Year January 2010
Abstract 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 ~\cite{nog,PCH,M-P_LSH,mvh}, and derive theoretical formulae in accuracy and memory amount. We compare simulated values with experimented values.
Back to list