Persistence based online signal and trajectory simplification for mobile devices
Authors:
Open Access
- 4 November 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 371-380
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.Keywords
Funding Information
- NSF (CNS-1217823, DMS-1221339, DMS-1418255)
This publication has 33 references indexed in Scilit:
- Segmentation of Trajectories on Non-Monotone Criteria2013
- Median TrajectoriesAlgorithmica, 2012
- A Fast $O(N)$ Multiresolution Polygonal Approximation Algorithm for GPS Trajectory SimplificationIEEE Transactions on Image Processing, 2012
- Efficient real-time trajectory trackingThe VLDB Journal, 2011
- DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIESInternational Journal of Computational Geometry & Applications, 2011
- Speeding up simplification of polygonal curves using nested approximationsPattern Analysis and Applications, 2008
- Understanding individual human mobility patternsNature, 2008
- Spatio-temporal data reduction with deterministic error boundsThe VLDB Journal, 2006
- A barcode shape descriptor for curve point cloud dataComputers & Graphics, 2004
- Topological Persistence and SimplificationDiscrete & Computational Geometry, 2002