Japanese / English

Detail of Publication

Text Language Japanese
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 or not Not reviewed
Presentation type Oral
Month & Year February 2013
Abstract 本稿では,高次元かつ大規模なデータセットを高速かつ省メモリで扱うための近似最近傍探索手法を提案する.近似最近傍探索は,入力ベクトルに最も距離が近いベクトルを探索する最近傍探索問題において,探索誤りを許容することで計算時間,メモリ使用量を大幅に削減するものである.ハッシュ構造を用いてクエリからの距離を推定する手法に改良を加え,より一般的なデータに対して,高速に解を得られるようになった.また,ベクトルを量子化表現することでメモリ使用量を削減した.実験では大規模なSIFT特徴とGIST特徴のデータセットを用いて精度,処理時間,メモリ使用量の観点で比較を行い,最近の既存手法と比べて高速に最近傍点を得られることを確認した.
Back to list