Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \mathbb{R}^d$, the closest point (in terms of Euclidean distance) is returned.

What is the best known query time on this problem in terms of $n$ and $d$ for data structures with near-linear size (or at worst polynomial size)? Note that solutions requiring space exponential in $d$ are not acceptable.

Perhaps I'm missing an obvious reference here, but is there anything of the form $O(2^{O(d)}\mbox{polylog}(n))$, given the space requirements?

For approximate NN, the best bounds are given by results of Arya, Mount, and colleagues. For slightly different requirements, the best results are given by Andoni-Indyk's Locality Sensitive Hashing.

If the space has a bounded expansion constant $c$ (aka doubling measure), then results of Karger & Ruhl, Clarkson, and several follow-up works (Navigating nets, Cover trees) give a query time of $O(c^{12}\log{n})$ with linear space. However, a pointset in $\mathbb{R}^d$ does not necessarily have a bounded expansion constant (in terms of $d$). In particular, the set $\{2^i:\quad i=1,\ldots,n\}$ has $c=O(n)$, despite lying in $\mathbb{R}^1$. The Assouad (doubling) dimension does not have this problem, but as far as I know, all results based on this dimension are for approximate NN.

Surely this must be known, but the older work on NN (eg by Clarkson or Meiser) generally requires exponential space, and newer work mostly focuses on the approximate NN problem or has some extra requirements on the space.

  • 1
    $\begingroup$ Take $O(n^2)$ equidistant hyperplanes (i.e. for every pair, the hyperplane of points equidistant to the points), then do $O(n)$ queries to find your NN. Is there a reason that this strategy is no good, other than the fact that you want to use less than $O(n^2d)$ space? $\endgroup$ – Andrew D. King Aug 18 '11 at 23:12
  • 1
    $\begingroup$ @Andrew a) This method is too slow. b) Storing the hyperplanes is unnecessary so there isn't actually any space overhead. $\endgroup$ – James King Aug 20 '11 at 18:29
  • $\begingroup$ @Lawrence, Yes, I see your point. How about this: Keep $N$ trees, one for each point, that orders the rest of the points (w.r.t. euclidean distance in $\mathbb{R}^d$) relative to the reference? This is horrible of course, but it meets your $O(N^2)$ space and $O(\ln N)$ NN lookup criteria. $\endgroup$ – user834 Aug 27 '11 at 19:00
  • $\begingroup$ Be more specific on how coordinates are stored. If they are just bits than you can interleave them, sort to implicitly get them in Morton order, then do an ANSV on common high bits to build an implicit quadtree. O(nlogn * d * (bits per dimension)) However, Vaidya was first to publish I believe: springerlink.com/content/p4mk2608787r7281 $\endgroup$ – Chad Brewbaker Jan 5 '12 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.