Abstract
We present efficient algorithms for segmenting and classifying a trajectory based on a parameterized movement model like the Brownian bridge movement model. Segmentation is the problem of subdividing a trajectory into parts such that each art is homogeneous in its movement characteristics. We formalize this using the likelihood of the model parameter. We consider the case where a discrete set of m parameter values is given and present an algorithm to compute an optimal segmentation with respect to an information criterion in O(nm) time for a trajectory with n sampling points. Classification is the problem of assigning trajectories to classes. We present an algorithm for discrete classification given a set of trajectories. Our algorithm computes the optimal classification with respect to an information criterion in O(m^2 + mk(log m + log k)) time for m parameter values and k trajectories, assuming bitonic likelihood functions.
Original language | English |
---|---|
Title of host publication | 30th European Workshop on Computational Geometry (EuroCG 2014, Ein-Gedi, Israel, March 3-5, 2014) |
Pages | 1-4 |
Publication status | Published - 2014 |
Event | 30th European Workshop on Computational Geometry (EuroCG 2014) - Dead Sea, Israel Duration: 3 Mar 2014 → 5 Mar 2014 Conference number: 30 https://www.cs.bgu.ac.il/~eurocg14/ |
Workshop
Workshop | 30th European Workshop on Computational Geometry (EuroCG 2014) |
---|---|
Abbreviated title | EuroCG 2014 |
Country | Israel |
City | Dead Sea |
Period | 3/03/14 → 5/03/14 |
Internet address |