Maximum Physically Consistent Trajectories

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 \log n \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(n k^2 \log k)\) 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.

Corresponding Publications

Maximum Physically Consistent Trajectories

Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, Frank Staals

Proc. 27th International Conference on Advances in Geographic Information Systems, 2019

Won Best Paper at SIGSPATIAL ’19
@inproceedings{trajectoryoutliers2019,
  author = {Custers, Bram and van de Kerkhof, Mees and Meulemans, Wouter and
                 Speckmann, Bettina and Staals, Frank},
  title = {Maximum Physically Consistent Trajectories},
  booktitle = {Proc. 27th International Conference on Advances in Geographic
                   Information Systems},
  series = {SIGSPATIAL '19},
  year = {2019},
  location = {Chicago, Illinois},
  numpages = {10},
  pages = {79--88},
  publisher = {ACM},
  category = {trajectories},
  doi = {10.1145/3347146.3359363},
  url = {https://dl.acm.org/authorize?N690079},
  note = {Won Best Paper at SIGSPATIAL '19},
}