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

言語	日本語
種類	研究会等の予稿
著者	武藤大志，多田匡志，岩村雅一，黄瀬浩一
論文名	ハッシュを利用した近似最近傍探索における隣接バケット参照の精度とメモリ使用量の理論式の導出
論文誌名	電子情報通信学会技術研究報告
Vol.	109
No.	374
発表番号	PRMU2009-170
ページ	pp.109-114
年月	2010年1月
分野	最近傍探索
キー	`Muto2010` (id=1131)

要約

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

この文献を出力

書式出力言語

書式の定義

書式の定義の書き方

{authors} のように波括弧でフィールドを挿入します．[ ... ] で囲んだ部分は，その中のフィールドが空のとき丸ごと省略されます．使えるフィールド：

{authors}{authors_and}{authors_ja}{authors_ja_tight}{authors_en}{authors_en_and}{authors_tight}{first_author}{title}{title_ja}{title_en}{journal}{journal_ja}{journal_en}{book_title}{volume}{number}{series}{presen_id}{pages}{pp}{num_pages}{year}{month}{month_en}{month_short}{ym}{date}{date_ja}{date_en}{publisher}{address}{location}{review}{review_ja}{review_en}{reviewed_mark}{presen_type}{type}{type_label}{doi}{url}{key}{awards}

出力結果

@inproceedings{Muto2010, author = {武藤, 大志 and 多田, 匡志 and 岩村, 雅一 and 黄瀬, 浩一}, title = {ハッシュを利用した近似最近傍探索における隣接バケット参照の精度とメモリ使用量の理論式の導出}, booktitle = {電子情報通信学会技術研究報告}, year = 2010, month = jan, volume = {109}, number = {374}, pages = {109--114}, note = {PRMU2009-170} }

← 一覧に戻る

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

要約

関連ファイル

この文献を出力