Bounded Quadrant System

Error-bounded trajectory compression on the go

Jiajun Liu, Kun Zhao, Philipp Sommer, Shuo Shang, Brano Kusy, Raja Jurdak

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

28 Citations (Scopus)

Abstract

Long-term location tracking, where trajectory compression is commonly used, has gained high interest for many applications in transport, ecology, and wearable computing. However, state-of-the-art compression methods involve high space-time complexity or achieve unsatisfactory compression rate, leading to rapid exhaustion of memory, computation, storage and energy resources. We propose a novel online algorithm for error-bounded trajectory compression called the Bounded Quadrant System (BQS), which compresses trajectories with extremely small costs in space and time using convex-hulls. In this algorithm, we build a virtual coordinate system centered at a start point, and establish a rectangular bounding box as well as two bounding lines in each of its quadrants. In each quadrant, the points to be assessed are bounded by the convex-hull formed by the box and lines. Various compression error-bounds are therefore derived to quickly draw compression decisions without expensive error computations. In addition, we also propose a light version of the BQS version that achieves O(1) complexity in both time and space for processing each point to suit the most constrained computation environments. Furthermore, we briefly demonstrate how this algorithm can be naturally extended to the 3-D case. Using empirical GPS traces from flying foxes, cars and simulation, we demonstrate the effectiveness of our algorithm in significantly reducing the time and space complexity of trajectory compression, while greatly improving the compression rates of the state-of-the-art algorithms (up to 47%). We then show that with this algorithm, the operational time of the target resource-constrained hardware platform can be prolonged by up to 41%.

Original languageEnglish
Title of host publicationICDE 2015
Subtitle of host publicationProceedings of the 2015 IEEE 31st International Conference on Data Engineering
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages987-998
Number of pages12
ISBN (Electronic)9781479979639, 9781479979646
ISBN (Print)9781479979653
DOIs
Publication statusPublished - 26 May 2015
Externally publishedYes
Event2015 31st IEEE International Conference on Data Engineering, ICDE 2015 - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015

Other

Other2015 31st IEEE International Conference on Data Engineering, ICDE 2015
CountryKorea, Republic of
CitySeoul
Period13/04/1517/04/15

Fingerprint Dive into the research topics of 'Bounded Quadrant System: Error-bounded trajectory compression on the go'. Together they form a unique fingerprint.

  • Cite this

    Liu, J., Zhao, K., Sommer, P., Shang, S., Kusy, B., & Jurdak, R. (2015). Bounded Quadrant System: Error-bounded trajectory compression on the go. In ICDE 2015: Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (pp. 987-998). Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICDE.2015.7113350