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$ at each round $r\ge 1$ and the goal is to find the point closest to $s_r$ in $S$, possibly in an approximate way, according to the Euclidean distance.

Question: How can we preprocess and organize the information of the sequences 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?

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?