Japanese / English

Detail of Publication

Text Language Japanese
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 or not Not reviewed
Presentation type Oral
Month & Year September 2011
Abstract 登録されたデータからクエリに最も近いものを探し出す最近傍探索問題では, 探索誤りを許容することで計算時間を大幅に削減することができ,これを近似 最近傍探索問題と呼ぶ. 近似最近傍探索は一般に, 最近傍点となる確率の高い点を選択し, それらとクエリとの距離を計算するという 2段階の処理で実現され,前者が手法の良し悪しを決定する. 本稿では,この処理で用いる「概算距離」を計算量を増やすことなく, より高精度に推定することにより, 高精度かつ高速な近似最近傍探索,を実現する手法を提案する. 実験の結果, $50\%$の精度で比較すると従来手法[1]と比べて,64次元のデータで約4倍,256次元のデータで約2.5倍の処理速度を得ることが確認できた.
Back to list