Random projections and sampling algorithms for clustering of high-dimensional polygonal curves

Stefan Meintrup, Alexander Munteanu, Dennis Rohde

Abstract

We study the $k$-median clustering problem for high-dimensional polygonal curves with a finite but unbounded number of vertices. We tackle the computational issues arising from high dimensionality by defining a Johnson-Lindenstrauss (JL) projection specifically for polygonal curves. We analyze the resulting error in terms of the Fréchet distance, a natural dissimilarity measure for curves. Our clustering algorithms achieve sublinear dependency on the number of input curves via subsampling. Additionally, we demonstrate that the Fréchet distance cannot be approximated within any factor less than $\sqrt{2}$ by reducing the vertex complexity of the curves. To evaluate our results, we provide a fast, CUDA-parallelized version of the Alt and Godau algorithm for computing the Fréchet distance.

Introduction

In modern data science, multivariate time-series data—such as geophysical sensor readings, financial trends, or technical monitoring logs—are often modeled as polygonal curves in high-dimensional space. Analyzing these curves requires robust distance measures like the Fréchet distance, which accounts for the continuous nature of the paths. However, as the number of curves ($n$), dimensions ($d$), and vertices ($m$) increase, traditional clustering becomes computationally prohibitive. This paper presents a framework to overcome the "curse of dimensionality" using random projections, sublinear sampling, and GPU acceleration.

Methodology

Dimension Reduction via JL Projections

The authors extend the Johnson-Lindenstrauss lemma to the domain of polygonal curves. By projecting high-dimensional vertices into a lower-dimensional subspace and reconnecting them, the geometric structure of the curve is preserved. The theoretical analysis shows that the Fréchet distance in the projected space maintains the original distance within a small multiplicative factor and an additive error term.

Sublinear Clustering

To avoid the $O(n^2)$ complexity of comparing every curve in a dataset, the researchers employ a sampling-based approach for $k$-median clustering. By selecting a small random "candidate set" of potential centers and a "witness set" for evaluation, they achieve a $(1+\epsilon)$-approximation with sublinear effort relative to the total number of curves.

GPU-Accelerated Fréchet Distance

The core bottleneck in curve clustering is the distance calculation. The authors developed a parallelized version of the Alt and Godau algorithm, specifically optimizing the "free-space diagram" computation for NVIDIA GPUs using CUDA. This engineering effort is critical for making high-dimensional clustering feasible in practice.

Theoretical Insights: The Additive Error Trade-off

A key finding is that JL projections for curves introduce an additive error related to $\alpha$, the length of the longest edge in the curve. This implies that the projection is most effective for "smooth" curves with uniform edge lengths.

Empirical relative error as a function of the longest edge length (alpha) and target precision (epsilon).

Furthermore, the authors prove a lower bound: it is impossible to simplify the number of vertices ($m$) significantly without losing substantial accuracy (specifically, a factor of $\sqrt{2}$). This justifies focusing optimization efforts on $d$ and $n$ rather than vertex reduction.

Experimental Results

The proposed methods were tested on real-world datasets, including hydraulic test rig data (6000-dimensional space) and weather simulations. The results confirmed that the combination of random projections and GPU parallelization yields massive performance gains.

Performance evaluation showing (a) empirical distortion and (b) running-time speedups across different algorithm variants.

Key Findings:

  • Massive Speedup: The parallelized approach achieved up to a 100x speedup over sequential implementations. Tasks that previously took hours were completed in under a minute.
  • Tight Approximations: Empirical distortion was consistently lower than theoretical worst-case bounds. Even with significant dimension reduction, the error rarely exceeded the user-defined margin.
  • Scalability: The sampling-based 1-median clustering proved robust, demonstrating that a constant number of samples is often sufficient to identify near-optimal cluster centers in large datasets.

Conclusion

By integrating theoretical guarantees with high-performance computing, this work provides a scalable solution for clustering complex, high-dimensional trajectories. While the additive error remains a constraint for curves with extreme edge lengths, the framework offers a significant leap forward for multivariate time-series analysis. Future research may explore data-aware projections to further mitigate approximation errors.

Summary updated

Abstract

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.
BibTeX
@inproceedings{meintrup2019random,
  author = {Stefan Meintrup and Alexander Munteanu and Dennis Rohde},
  title = {{Random projections and sampling algorithms for clustering of high-dimensional polygonal curves}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=dMTt1x7l7oN},
}
Figure