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?