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

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
Title of host publicationProceedings of 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
PublisherACM
Pages371-380
Number of pages10
ISBN (Print)978-1-4503-3131-9
DOIs
Publication statusPublished - 7 Nov 2014

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