Spatio-temporal Data Reduction with Deterministic Error Bounds

Hu Cao*, Ouri Wolfson, Goce Trajcevski

*Corresponding author for this work

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

19 Scopus citations


A common way of storing spatio-temporal information about mobile devices is in the form of a 3D (2D geography + time) trajectory. We argue that when cellular phones and Personal Digital Assistants become location-aware, the size of the spatio-temporal information generated may prohibit efficient processing. We propose to adopt a technique studied in computer graphics, namely line-simplification, as an approximation technique to solve this problem. Line simplification uses a distance function in producing the trajectory approximation. We postulate the desiderata for such a distance: it should be sound, namely the error of the answers to spatio-temporal queries must be bounded. We analyze several distances, and prove that some are sound in this sense for some types of queries, while others are not. Interestingly, not a single distance analyzed proves to be sound for all the common spatio-temporal queries, and therefore multi-distance line-simplification is introduced and analyzed. Then we propose an aging mechanism which gradually shrinks the size of the trajectories as time progresses. Finally, we analyze experimentally the effectiveness of line-simplification in reducing the size of a trajectories database.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC 2003
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Print)1581137656, 9781581137651
StatePublished - 2003
EventProceedings of the 2003 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC 2003 - San Diego, CA, United States
Duration: Sep 19 2003Sep 19 2003

Publication series

NameProceedings of the Joint Workshop on Foundations of Mobile Computing


OtherProceedings of the 2003 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC 2003
Country/TerritoryUnited States
CitySan Diego, CA


  • Line Simplification
  • Moving Objects Database

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Spatio-temporal Data Reduction with Deterministic Error Bounds'. Together they form a unique fingerprint.

Cite this