# Binary Trees for Nearest Neighbor Search

Given points $$x_1, ..., x_n \in \mathbb{R}^d$$, consider a binary decision tree $$T$$ on $$\mathbb{R}^d$$ with $$L$$ leaves, i.e. for a point $$y \in \mathbb{R}^d$$ at every node of the tree, we check whether $$y_i \le c$$. Every leaf of $$T$$ is associated with exactly one of the $$n$$ points.

For any new point $$y \in \mathbb{R}^d$$, we write $$x(y)$$ for the point associated with the leaf that $$y$$ ends up in.

The aim is to construct $$T$$ such that $$x(y)$$ is a good guess of the point that is closest to $$y$$, i.e. we want to find $$T$$ such that for any $$y \in \mathbb{R}^d$$

$$\|y - x(y)\|_2 \le (1+\epsilon) \min_{j \in [n]} \|x_j - y\|_2$$ for some small $$\epsilon > 0$$.

Naturally, the larger $$L$$ the smaller $$\epsilon$$ may become. And the easier it is to separate the points $$x_1,...,x_n$$ with a tree, the smaller $$L$$ may be.

My Questions:

• What is an algorithm that performs this task?
• In particular, given $$n,d,\epsilon$$, are there worst-case bounds on how many leaves $$L$$ we need?
• The other way around, given $$L, n, d$$, what can we say about $$\epsilon$$?

Of course, even for just $$n=2$$ points, we can only hope for an approximate solution since the set $$\Big\{\|y-x_1\| = \|y-x_2\| \Big\}$$ will be a general hyperplane (and is thus not axis aligned).

$$O(n/\varepsilon^d)$$: total size
$$d^{O(1)} \log n$$: query time