# Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance

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?

• I think this type of problem usually goes under the name (vector) quantization. There are some well established preprocessing approaches, e.g., k-d trees. Since nearest-neighbor models are standard examples in machine learning, you can find lots of useful explainers online (I found some by googling "nearest neighbor quantization k-d trees"). Feb 23, 2021 at 16:12
• $p_r=s_r$?$\,\,\,\,\,\,\,$ Feb 23, 2021 at 16:58
• @DieterKadelka thank you for your question. No, we just have to find the closest point in $S$ at each round and the main computational issue is that $S$ is too large to check all points it contains. Feb 23, 2021 at 17:35
• Maybe I'm confused. I don't think you can mean "find the point closest to $s_r$ in $S$". Probably you mean "find the point in $S$ which is closest to $p_r$"? Feb 23, 2021 at 19:51
• OK @MichaelEngelhardt I will think about it. I have the feeling that if we have an (adversarial arrangements of points) similar somewhat to the one I attempted to describe here mathoverflow.net/q/383900/115803, it is still unlikely this strategy can work, but maybe I am wrong. In any case, it would be interesting and useful to find a rigorous characterization of these adversarial point arrangements in $S$, to be able to identify a wide class of inputs where this operations can be done in a computational efficient way. Feb 23, 2021 at 21:04

Almost all algorithms for proximity problems in high-dimensional spaces proceed by reducing the problem to the problem of finding an approximate near neighbor, which is the decision version of the approximate nearest-neighbor problem. [...] All the NNS algorithms are based on space partitions (even if not always framed this way). We distinguish two broad classes of partitions: 1) data-independent approaches, where the partition is independent of the given dataset $$P$$, and 2) data-dependent approaches, where the partition depends on the dataset $$P$$.