0
$\begingroup$

We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$.

In the problem I am trying to solve, in a sequential fashion, we obtain a new sequence $s_r$ at each round $r\ge 1$ and the goal is to find the sequence closest to $s_r$ in $S$, possibly in an approximate way. The distance between two sequences is the Euclidean distance. 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 and randomized algorithms/data structures. Is there in the related literature any solution already found for this problem?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.