Consider a set of S of n data points in real d-dimensional space, R^d, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q∈ R^d, is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R^d in O(dn log n) time and O(dn) space, so that given a query point q ∈ R^d, and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O(c_{d, ϵ} log n) time, where c_d,ϵ≤d ⌈1 + 6d/ϵ⌉^d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n) time.