Persistence based online signal and trajectory simplification for mobile devices

Panagiota Katsikouli, Rik Sarkar, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

We describe an online algorithm to simplify large volumes of location and sensor data on the source mobile device, by eliminating redundant data points and saving important ones. Our approach is to use topological persistence to identify large scale sharp features of a data stream. We show that for one-dimensional data streams such as trajectories, simplification based on topologically persistent features can be maintained online, such that each new data-point is processed in O(1) time. Our method extends to multi-resolution simplifications, where it identifies larger scale features that represent more important elements of data, and naturally eliminates noise and small deviations. The multi-resolution simplification is also maintained online in real time, at cost of O(1) per input point. Therefore it is lightweight and suitable for use in embedded sensors and mobile phones. The method can be applied to more general data streams such as sensor data to produce similar simplifications. Our experiments on real data show that this approach when applied to the curvature function of trajectory or sensor data produces compact simplifications with low approximation errors comparable to existing offline methods.

Original languageEnglish (US)
Title of host publication22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014
EditorsMarkus Schneider, Michael Gertz, Yan Huang, Jagan Sankaranarayanan, John Krumm
PublisherAssociation for Computing Machinery
Pages371-380
Number of pages10
ISBN (Electronic)9781450331319
DOIs
StatePublished - Nov 4 2014
Externally publishedYes
Event22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014 - Dallas, United States
Duration: Nov 4 2014Nov 7 2014

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Volume04-07-November-2014

Conference

Conference22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014
Country/TerritoryUnited States
CityDallas
Period11/4/1411/7/14

All Science Journal Classification (ASJC) codes

  • Earth-Surface Processes
  • Computer Science Applications
  • Modeling and Simulation
  • Computer Graphics and Computer-Aided Design
  • Information Systems

Keywords

  • Geometry
  • Mobile sensing
  • Persistence
  • Spatial data
  • Trajectory simplification

Fingerprint

Dive into the research topics of 'Persistence based online signal and trajectory simplification for mobile devices'. Together they form a unique fingerprint.

Cite this