<p>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.</p>

<p>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.</p>

<p>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?</p>

<p>For <strong>approximate</strong> 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.</p>

<p>If the space has a <strong>bounded expansion constant</strong> $c$ (aka doubling measure), then results of Karger &amp; 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-05T17:03:15.280Z
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: http://www.springerlink.com/content/p4mk2608787r7281/
Chad Brewbaker
CC BY-SA 3.0
2011-08-18T23:12:15.437Z
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?
Andrew D. King
CC BY-SA 3.0
2011-08-20T18:29:23.253Z
@Andrew  a) This method is too slow.  b) Storing the hyperplanes is unnecessary so there isn't actually any space overhead.
James King
CC BY-SA 3.0
2011-08-27T19:00:23.343Z
@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.
user834
<ds.data-structures><cg.comp-geom>
Exact nearest neighbor in $d$-dimensional Euclidean space
Lawrence Cayton
# Exact nearest neighbor in $d$-dimensional Euclidean space

(Asked by: username_0 on 2011-08-18)

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.

**Tags:** ds.data-structures, cg.comp-geom
> **Comments:**
> **username_2**: 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?  
> **username_3**: @Andrew  a) This method is too slow.  b) Storing the hyperplanes is unnecessary so there isn't actually any space overhead.  
> **username_4**: @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.  
> **username_1**: 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: http://www.springerlink.com/content/p4mk2608787r7281/  

---

## 0 answers

