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?


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.