8 papers
Time Series Decomposition using the Fréchet Distance
Anne Driemel, Jan Höckendorff, Ioannis Psarros +1
In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of base curves of length at most such that t…
Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
Anne Driemel, Jan Höckendorff, Ioannis Psarros +2
Given a finite metric space the -median problem is to find a set of centers that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c…
Property Testing of Curve Similarity
Peyman Afshani, Maike Buchin, Anne Driemel +2
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is gi…
A near-linear time approximation scheme for -median clustering under discrete Fréchet distance
Anne Driemel, Jan Höckendorff, Ioannis Psarros +1
A time series of complexity is a sequence of real valued measurements. The discrete Fréchet distance is a distance measure between two time series and $y…
Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better
Jacobus Conradi, Anne Driemel
Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation…
Range Counting Oracles for Geometric Problems
Anne Driemel, Morteza Monemizadeh, Eunjin Oh +2
In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size in a disc…