While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and @math , few non-trivial algorithms are known for @math when ( @math ). In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the first non-trivial approximation factor guarantees in this setting.
 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 The key to the algorithm is a locality-sensitive hash: a mapping h: Rd → U with the property that h(x) = h(y) is much more likely for nearby x, y. We introduce a somewhat regular simplex which tessellates Rd, and efficiently hash each point in any simplex of this tessellation to all d + 1 corners; any points in neighboring cells will be hashed to a shared corner and noticed as nearby points. This method is completely independent of dimension reduction, so that additional space and time savings are available by first reducing all input vectors. Abstract Given n points in d dimensions, we show how to construct a data structure of space O( d 2 d n ) that approximately answers closest-point queries in time O( d 2 d log n ). The returned point is at most O (d> 1 2 ) times further from the query point than the true closest point. We also show how to construct a data structure of space O( dn log m ), that—with high probability—can answer a sequence of m closest-point queries in time O( d log n log m ) per query, with approximation ratio O (d 3 2 ) . Our data structures are based on quadtrees.