<p>This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed quadtree. Anyway, the currents bounds known are</p>
<p><span class="math-container">$O(n/\varepsilon^d)$</span>: total size</p>
<p><span class="math-container">$d^{O(1)} \log n$</span>: query time</p>
<p>See this paper:
<a href="https://dl.acm.org/doi/10.1145/509907.510011" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/509907.510011</a></p>
<p>These authors had extensive followup work on trading query time for space, etc.</p>

CC BY-SA 4.0
2022-03-03T02:41:50.927Z
2022-03-03T02:41:50.927Z
Sariel Har-Peled
<p>Given points <span class="math-container">$x_1, ..., x_n \in \mathbb{R}^d$</span>, consider a binary decision tree <span class="math-container">$T$</span> on <span class="math-container">$\mathbb{R}^d$</span> with <span class="math-container">$L$</span> leaves, i.e. for a point <span class="math-container">$y \in \mathbb{R}^d$</span> at every node of the tree, we check whether <span class="math-container">$y_i \le c$</span>. Every leaf of <span class="math-container">$T$</span> is associated with exactly one of the <span class="math-container">$n$</span> points.</p>
<p>For any new point <span class="math-container">$y \in \mathbb{R}^d$</span>, we write <span class="math-container">$x(y)$</span> for the point associated with the leaf that <span class="math-container">$y$</span> ends up in.</p>
<p>The aim is to construct <span class="math-container">$T$</span> such that <span class="math-container">$x(y)$</span> is a good guess of the point that is closest to <span class="math-container">$y$</span>, i.e. we want to find <span class="math-container">$T$</span> such that for any <span class="math-container">$y \in \mathbb{R}^d$</span></p>
<p><span class="math-container">$$\|y - x(y)\|_2 \le (1+\epsilon) \min_{j \in [n]} \|x_j - y\|_2$$</span>
for some small <span class="math-container">$\epsilon &gt; 0$</span>.</p>
<p>Naturally, the larger <span class="math-container">$L$</span> the smaller <span class="math-container">$\epsilon$</span> may become. And the easier it is to separate the points <span class="math-container">$x_1,...,x_n$</span> with a tree, the smaller <span class="math-container">$L$</span> may be.</p>
<p>My Questions:</p>
<ul>
<li>What is an algorithm that performs this task?</li>
<li>In particular, given <span class="math-container">$n,d,\epsilon$</span>, are there worst-case bounds on how many leaves <span class="math-container">$L$</span> we need?</li>
<li>The other way around, given <span class="math-container">$L, n, d$</span>, what can we say about <span class="math-container">$\epsilon$</span>?</li>
</ul>
<p>Of course, even for just <span class="math-container">$n=2$</span> points, we can only hope for an approximate solution since the set <span class="math-container">$\Big\{\|y-x_1\| = \|y-x_2\| \Big\}$</span> will be a general hyperplane (and is thus not axis aligned).</p>

<computational-geometry><tree><decision-trees><near-neighbors>
Binary Trees for Nearest Neighbor Search
Claudio Moneo
# Binary Trees for Nearest Neighbor Search

(Asked by: username_0 on 2022-02-28)

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).

**Tags:** computational-geometry, tree, decision-trees, near-neighbors


---

## 1 answers

### Answer by username_1 on 2022-03-03. Score: 2 | Accepted answer

This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed quadtree. Anyway, the currents bounds known are

$O(n/\varepsilon^d)$: total size

$d^{O(1)} \log n$: query time

See this paper:
<https://dl.acm.org/doi/10.1145/509907.510011>

These authors had extensive followup work on trading query time for space, etc.


---

