  We study the $k$-median clustering problem for high-dimensional polygonal
curves with finite but unbounded number of vertices. We tackle the
computational issue that arises from the high number of dimensions by defining
a Johnson-Lindenstrauss projection for polygonal curves. We analyze the
resulting error in terms of the Fr\'echet distance, which is a tractable and
natural dissimilarity measure for curves. Our clustering algorithms achieve
sublinear dependency on the number of input curves via subsampling. Also, we
show that the Fr\'echet distance can not be approximated within any factor of
less than $\sqrt{2}$ by probabilistically reducing the dependency on the number
of vertices of the curves. As a consequence we provide a fast,
CUDA-parallelized version of the Alt and Godau algorithm for computing the
Fr\'echet distance and use it to evaluate our results empirically.
