A locality-sensitive hash for real vectors
Tyler Neylon · 2010
We present a simple and practical algorithm for the c--approximate near neighbor problem (c--NN): given n points P ⊂ Rd and radius R, build a data structure which, given q ∈ Rd, can with probability 1 -- δ return a point p e P with dist(p, q) ≤ cR if there is any p* e P with dist(p*, q) ≤ R. For c = d + 1, our algorithm deterministically (δ = 0) preprocesses in time O(nd log d), space O(dn), and answers queries in expected time O(d2); this is the first known algorithm to deterministically guarantee an O(d)---NN solution in constant time with respect to n for all lp metrics. A probabilistic version empirically achieves useful c values (c