2
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ 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"). $\endgroup$
    – Yoav Kallus
    Commented Feb 23, 2021 at 16:12
  • 1
    $\begingroup$ $p_r=s_r$?$\,\,\,\,\,\,\,$ $\endgroup$
    – James Martin
    Commented Feb 23, 2021 at 16:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Penelope Benenati
    Commented Feb 23, 2021 at 17:35
  • 1
    $\begingroup$ 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$"? $\endgroup$
    – James Martin
    Commented Feb 23, 2021 at 19:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Penelope Benenati
    Commented Feb 23, 2021 at 21:04

1 Answer 1

Reset to default
3
$\begingroup$

This is a complex but well-studied topic. Perhaps starting here (Chapter 43) will help you focus on your particular application:

Andoni, Alexandr, and Piotr Indyk. "Nearest neighbors in high-dimensional spaces." Handbook of Discrete and Computational Geometry. (2017). PDF of preliminary version of Ch.43.

Here's a little snippet:

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the reference. I will read it carefully. $\endgroup$
    – Penelope Benenati
    Commented Feb 23, 2021 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .