Publications
CONFERENCE (INTERNATIONAL) 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)
September 28, 2021
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 (external link)