We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$. 

In the problem I am trying to solve, in a sequential fashion, we obtain a *new* point $p_r\not\in S$ at each round $r\ge 1$ and the goal is to find the point $s_r\in S$ closest to $p_r$ in $S$, possibly in an approximate way, according to the Euclidean distance. 

---

**Question:** How can we preprocess and organize the information of the points in $S$, to solve this problem focusing on the trade-off between time complexity and distance minimization? 
 
I guess we can use sampling techniques and randomized algorithms/data structures, to obtain a solution with theoretical performance guarantees in expectation (or with high probability) over the internal algorithmic randomization. Is there in the related literature any solution already found for this problem?