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?

  • 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$
    – John L.
    Commented Jun 16, 2019 at 21:16

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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