## Abstract

Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n logn log
^{2}k) time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk) time algorithm for any model where consistency is "concatenable": a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models which are not concatenable. We show how to compute the maximum subsequence for such models in O(nk
^{2}logk) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets.

Original language | English |
---|---|

Title of host publication | SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems |

Editors | Farnoush Banaei-Kashani, Goce Trajcevski, Ralf Hartmut Guting, Lars Kulik, Shawn Newsam |

Place of Publication | New York |

Publisher | Association for Computing Machinery, Inc |

Pages | 79-88 |

Number of pages | 10 |

ISBN (Electronic) | 9781450369091 |

ISBN (Print) | 978-1-4503-6909-1 |

DOIs | |

Publication status | Published - 5 Nov 2019 |

Event | 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - Chicago, IL, United States Duration: 5 Nov 2019 → 8 Dec 2019 http://sigspatial2019.sigspatial.org/ |

### Conference

Conference | 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems |
---|---|

Abbreviated title | ACM SIGSPATIAL 2019 |

Country/Territory | United States |

City | Chicago, IL |

Period | 5/11/19 → 8/12/19 |

Internet address |

## Keywords

- Algorithms
- Experiments
- Outlier detection
- Physics models