Publications
カンファレンス (国際) LGTM: A Fast and Accurate kNN Search Algorithm in High-dimensional Spaces
Yusuke Arai (Osaka univ.), Daichi Amagata (Osaka univ.), Sumio Fujita, Takahiro Hara (Osaka univ.)
The 32nd International Conference on Database and Expert Systems Applications (DEXA2021)
2021.9.28
Approximate k nearest neighbor (AkNN) search is a primitive operator for many applications, such as computer vision and machine learning. As these applications deal with a large set of high-dimensional points, a fast and accurate solution is required. It is known that graph- based AkNN search algorithms are faster and more accurate than other approaches, including hash- and quantization-based ones. However, existing graph-based AkNN search algorithms rely purely on heuristics, i.e., their performances are not theoretically supported. This paper proposes LGTM, a new algorithm for AkNN search, that exploits both locality- sensitive hashing and a proximity graph. The performance of LGTM is theoretically supported. Our experiments on real datasets show that LGTM outperforms state-of-the-art AkNN search algorithms.
Paper : LGTM: A Fast and Accurate kNN Search Algorithm in High-dimensional Spaces （外部サイト）