Fast and Memory Efficient Approximate Nearest Neighbor Search with Distance Estimation Based on Space Indexing
| Language | Japanese |
|---|---|
| Type | Proceedings of Japanese Conferences |
| Authors | Tomokazu Sato, Masakazu Iwamura, Koichi Kise |
| Title | Fast and Memory Efficient Approximate Nearest Neighbor Search with Distance Estimation Based on Space Indexing |
| Journal | IEICE |
| Vol. | 112 |
| No. | 441 |
| Presentation number | PRMU2012-142 |
| Pages | pp.73-78 |
| Location | 大阪府堺市 |
| Reviewed | Not reviewed |
| Presentation type | Oral |
| Date | February 2013 |
| Research fields | Nearest Neighbor Search |
| Key | Sato2013_IEICEPRMU (id=1335) |
Abstract
本稿では，高次元かつ大規模なデータセットを高速かつ省メモリで扱うための近似最近傍探索手法を提案する．近似最近傍探索は，入力ベクトルに最も距離が近いベクトルを探索する最近傍探索問題において，探索誤りを許容することで計算時間，メモリ使用量を大幅に削減するものである．ハッシュ構造を用いてクエリからの距離を推定する手法に改良を加え，より一般的なデータに対して，高速に解を得られるようになった．また，ベクトルを量子化表現することでメモリ使用量を削減した．実験では大規模なSIFT特徴とGIST特徴のデータセットを用いて精度，処理時間，メモリ使用量の観点で比較を行い，最近の既存手法と比べて高速に最近傍点を得られることを確認した．
Files
- …
Export this publication
Format definition
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:
{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}