AI Paper Atlas

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

NeurIPS 2019 · Learning theory and algorithms › Clustering · approach: Correlation clustering · 6 citations (OpenAlex)

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 changedWhereMeasuredEffect
Project curve vertices using the Johnson-Lindenstrauss embeddingFréchet distance computation on polygonal curves · All data setsdistortionImproved
Parallelize the distance algorithm with CUDAFréchet distance computation · Experiments across the evaluated data setsspeedup: factor of 10Improved
Project curve vertices to a lower-dimensional space before distance computationFréchet distance computation · Experiments across the evaluated data setsspeedup: factor of 10Improved
Combine random projection with CUDA parallelizationFréchet distance computation · Experiments across the evaluated data setsspeedup: factor 100Improved
Use PCA on vertices instead of random projectionFréchet distance computation on high-intrinsic-dimension simplex-generated curves · Simplex-generated curvesdistortionHurt
Use candidate and witness subsamplingFréchet 1-median clustering · Weather simulation datarunning timeImproved
Vary the sampling and random-projection approximation parametersFréchet 1-median sampling scheme · Weather simulation dataapproximation errorNo clear effect
Use uniform candidate and witness sampling without assumptions on the inputDiscrete Fréchet 1-median · Arbitrary input curvesapproximation factor: $(2+\varepsilon)$-approximationImproved
Use candidate sampling under the stated outlier assumptionDiscrete Fréchet 1-median · Inputs with the specified outlier fractionapproximation factor: $(1+\varepsilon)$-approximationImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy