Fast Approximate Nearest Neighbor Search Based on Improved Approximate Distance
| Language | Japanese |
|---|---|
| Type | Proceedings of Japanese Conferences |
| Authors | Tomokazu Sato, Masakazu Iwamura, Koichi Kise |
| Title | Fast Approximate Nearest Neighbor Search Based on Improved Approximate Distance |
| Journal | IEICE Technical Report |
| Vol. | 111 |
| No. | 193 |
| Presentation number | PRMU2011-67 |
| Pages | pp.61-66 |
| Location | 北海道函館市 |
| Reviewed | Not reviewed |
| Presentation type | Oral |
| Date | September 2011 |
| Research fields | Pattern recognition |
| Key | Sato2011_IEICEPRMU (id=1224) |
Abstract
登録されたデータからクエリに最も近いものを探し出す最近傍探索問題では， 探索誤りを許容することで計算時間を大幅に削減することができ，これを近似 最近傍探索問題と呼ぶ． 近似最近傍探索は一般に， 最近傍点となる確率の高い点を選択し， それらとクエリとの距離を計算するという 2段階の処理で実現され，前者が手法の良し悪しを決定する． 本稿では，この処理で用いる「概算距離」を計算量を増やすことなく， より高精度に推定することにより， 高精度かつ高速な近似最近傍探索，を実現する手法を提案する． 実験の結果， $50\%$の精度で比較すると従来手法[1]と比べて，64次元のデータで約4倍，256次元のデータで約2.5倍の処理速度を得ることが確認できた．
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}