0
$\begingroup$

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).

E.g. if the dates are [1, 2, 3, 4, 100] and I want to sample 3 elements, the ideal sample would be [1, 50.5, 100] and the closest available dates are [1, 4, 100].

Is this a known problem with an existing algorithm?

$\endgroup$

bumped to the homepage by Community yesterday

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 2
    $\begingroup$ Could you define your goal more clearly? Could you give more examples? For example, if the date are [1,2,3,4,5,6,7,8,9,10, 20,95,99,100] and you want to sample 5 elements, what should happen? What will be done to the chosen samples? $\endgroup$ – Apass.Jack Jun 16 at 21:16
0
$\begingroup$

I assume that for dates $d_1\leq d_2\leq\cdots\leq d_n$ you want $k>1$ samples of minimal total absolute distance from the ideal sample points $s_i=d_1+(i-1)(d_n-d_1)/(k-1)$, $i\in[k]$.

If you can repeat elements, just sample at $\operatorname{argmin}_{j\in[n]}|d_j-s_i|$ for each $i\in[n]$.

Without repeating elements the following dynamic program solves your problem in time $O(n^3)$ and space $O(n^2)$: let $M(i,j)$ be the minimal total absolute distance for $k-i+1$ samples chosen from $a_j,\ldots,a_n$ from the ideal samples $s_i,\ldots,s_k$. Distance $M$ satisfies \begin{align*} M(i,j) = \begin{cases} \min_{j\leq j'\leq n} |d_{j'}-s_i|+M(i+1,j'+1), & \text{$i\leq k$, $j\leq n$, }\\ 0, & \text{$i>k$},\\ \infty, & \text{otherwise}, \end{cases} \end{align*} and $M(1,1)$ is the minimum solution value.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.