Research map / Learning theory and algorithms / Clustering
Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves
Stefan Meintrup, Alexander Munteanu, Dennis Rohde
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Project curve vertices using the Johnson-Lindenstrauss embedding | Fréchet distance computation on polygonal curves · All data sets | distortion | Improved |
| Parallelize the distance algorithm with CUDA | Fréchet distance computation · Experiments across the evaluated data sets | speedup: factor of 10 | Improved |
| Project curve vertices to a lower-dimensional space before distance computation | Fréchet distance computation · Experiments across the evaluated data sets | speedup: factor of 10 | Improved |
| Combine random projection with CUDA parallelization | Fréchet distance computation · Experiments across the evaluated data sets | speedup: factor 100 | Improved |
| Use PCA on vertices instead of random projection | Fréchet distance computation on high-intrinsic-dimension simplex-generated curves · Simplex-generated curves | distortion | Hurt |
| Use candidate and witness subsampling | Fréchet 1-median clustering · Weather simulation data | running time | Improved |
| Vary the sampling and random-projection approximation parameters | Fréchet 1-median sampling scheme · Weather simulation data | approximation error | No clear effect |
| Use uniform candidate and witness sampling without assumptions on the input | Discrete Fréchet 1-median · Arbitrary input curves | approximation factor: $(2+\varepsilon)$-approximation | Improved |
| Use candidate sampling under the stated outlier assumption | Discrete Fréchet 1-median · Inputs with the specified outlier fraction | approximation factor: $(1+\varepsilon)$-approximation | Improved |
Closest papers by meaning
- Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms (JMLR 2024 · similarity 0.85)
- Near-Optimal Private and Scalable $k$-Clustering (NeurIPS 2022 · similarity 0.84)
- Subquadratic High-Dimensional Hierarchical Clustering (NeurIPS 2019 · similarity 0.84)
- Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves (ICML 2025 · similarity 0.84)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.83)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
