Fast Approximate near Neighbor Algorithm by Clustering in High Dimensions
Hung Tran-The, Vinh Nguyen Van, Minh Hoang Anh · 2015
This paper addresses the (r, 1 + ϵ)-approximate near neighbor problem ( or (r, 1 + v)-NN) that is defined as follows: given a set of n points in a d-dimensional space, a query point q and parameter 01+2ρ/1+2ρ + dn) space, and O(fdn 2ρ/1+2ρ) query time, where f is generally a small integer, ρ is a parameter of the algorithm in (STOC 1998) [1] or (STOC 2015) [2]. Our results show that we can improve the algorithms in [1], [2] when value ϵ is small (ϵ <; 1 for [1] and ϵ <; 0.5 for [2]).