Derivation of Theoretical Formulae of Accuracy and Memory Amount on Accessing Neighboring Buckets in Hash-Based Approximate Nearest Neighbor Search
Language
Japanese
Type
Proceedings of Japanese Conferences
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
Date
January 2010
Research fields
Nearest Neighbor Search
Key
Muto2010 (id=1131)
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.
Files
…
Export this publication
Tab-separated. Paste into the sheet starting at column A. Required fields that cannot be inferred are left blank.
Format definition
Edits apply immediately and stay in effect until you pick a style again or reset. First line is the default; add lines like "book: …" to override per type.
How to write the definition
Insert a field with braces like {authors}. A part enclosed in [ ... ] is omitted entirely when any field inside it is empty. Available fields:
One macro per line as \name{field}{field}…. A field name in braces is replaced by its (LaTeX-escaped) value; other text is kept. Rename macros or add lines freely — they appear in the macro selector. A line like master_thesis: thesis fixes the macro for a type (automatic choice: journals use paperdoi with a DOI, paperno with a number, else paper; conferences conf with pages, else confpaper; books book). {pages} comes as 119--124; {journal} falls back to the book title. Fields: