A framework for trajectory segmentation by stable criteria

S.P.A. Alewijnse, K. Buchin, M. Buchin, A. Kölzsch, H. Kruckenberg, M.A. Westenberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

24 Citations (Scopus)
62 Downloads (Pure)

Abstract

We present an algorithmic framework for criteria-based segmentation of trajectories that can efficiently process a large class of criteria. Criteria-based segmentation is the problem of subdividing a trajectory into a small number of parts such that each part satisfies a global criterion. Our framework can handle criteria that are stable, in the sense that these do not change their validity along the trajectory very often. This includes both increasing and decreasing monotone criteria. Our framework takes O(n log n) time for preprocessing and computation, where n is the number of data points. It surpasses the two previous algorithmic frameworks on criteria-based segmentation, which could only handle decreasing monotone criteria, or had a quadratic running time, respectively. Furthermore, we develop an efficient data structure for interactive parameter selection, and provide mechanisms to improve the exact position of break points in the segmentation. We demonstrate and evaluate our framework by performing case studies on real-world data sets.
Original languageEnglish
Title of host publication22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2014, Dallas, Texas, USA, November 4-7, 2014)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages351-360
ISBN (Print)978-1-4503-3131-9
DOIs
Publication statusPublished - 2014
Event22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014) - Dallas, United States
Duration: 4 Nov 20147 Nov 2014
Conference number: 22
http://sigspatial2014.sigspatial.org/

Conference

Conference22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014)
Abbreviated titleACM SIGSPATIAL 2014
CountryUnited States
CityDallas
Period4/11/147/11/14
Internet address

Fingerprint Dive into the research topics of 'A framework for trajectory segmentation by stable criteria'. Together they form a unique fingerprint.

  • Cite this

    Alewijnse, S. P. A., Buchin, K., Buchin, M., Kölzsch, A., Kruckenberg, H., & Westenberg, M. A. (2014). A framework for trajectory segmentation by stable criteria. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2014, Dallas, Texas, USA, November 4-7, 2014) (pp. 351-360). New York NY: Association for Computing Machinery, Inc. https://doi.org/10.1145/2666310.2666415