More Web Proxy on the site http://driver.im/

research-article

SQUISH: an online approach for GPS trajectory compression

Authors:

Jonathan Muckell,

Jeong-Hyon Hwang,

Catherine T. Lawson,

S. S. RaviAuthors Info & Claims

COM.Geo '11: Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications

Article No.: 13, Pages 1 - 8

https://doi.org/10.1145/1999320.1999333

Published: 23 May 2011 Publication History

Abstract

GPS-equipped mobile devices such as smart phones and in-car navigation units are collecting enormous amounts spatial and temporal information that traces a moving object's path. The popularity of these devices has led to an exponential increase in the amount of GPS trajectory data generated. The size of this data makes it difficult to transmit it over a mobile network and to analyze it to extract useful patterns. Numerous compression algorithms have been proposed to reduce the size of trajectory data sets; however these methods often lose important information essential to location-based applications such as object's position, time and speed. This paper describes the Spatial QUalIty Simplification Heuristic (SQUISH) method that demonstrates improved performance when compressing up to roughly 10% of the original data size, and preserves speed information at a much higher accuracy under aggressive compression. Performance is evaluated by comparison with three competing trajectory compression algorithms: Uniform Sampling, Douglas-Peucker and Dead Reckoning.

References

[1]

M. Abdelguerfi, J. Givaudan, K. Shaw, and R. Ladner. The 2-3tr-tree, a trajectory-oriented index structure for fully envolving valid-time spatio-temporal datasets. In 10th ACM-GIS, pages 29--34. ACM Press, 2002.

Digital Library

[2]

P. K. Agarwal, L. J. Guibas, H. Edelsbrunner, J. Erickson, M. Isard, S. HarPeled, J. Hershberger, C. Jensen, and L. Kavraki. Algorithmic issues in modeling motion. ACM Computing Surveys, 34:550--572, 2002.

Digital Library

[3]

D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.

[4]

M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424--436, 1993.

Digital Library

[5]

F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 330--339, New York, NY, USA, 2007. ACM.

Digital Library

[6]

S. P. Greaves and M. A. Figliozzi. Commerical vehicle tour data collection using passive gps technology: Issues and potential applications. Transportation Research Record, 2049:158--166, 2008.

[7]

J. Hershberger and J. Snoeyink. Speeding up the douglas-peucker line simplification algorithm, 1992.

[8]

C. Jones and J. Sedor. Improving the reliability of freight travel. Public Roads, 70(1), 2006.

[9]

E. McCormack and M. E. Hallenbeck. Its devices used to collect truck data for performance benchmarks. Transportation Research Record, 1957:43--50, 2006.

[10]

N. Meratnia and R. A. d. By. Spatiotemportal Compression Techniques for Moving Point Objects, volume 2992. Springer Berlin/Heidelberg, 2004.

[11]

J. Muckell, Q. Cao, P. Mackenzie, D. Messier, and J. Salvo. Toward an intelligent brokerage platform: Mining backhaul opportunities in telematics data. Transportation Research Record, 2097:1--8, 2009.

[12]

J. Muckell, J.-H. Hwang, C. T. Lawson, and S. S. Ravi. Algorithms for compressing gps trajectory data: an empirical evaluation. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS '10, pages 402--405, New York, NY, USA, 2010. ACM.

Digital Library

[13]

M. Potamias, K. Patroumpas, and T. Sellis. Sampling trajectory streams with spatiotemporal criteria. In 18th International Conference on Scientific and Statistical Database Management (SSDBM'06), pages 275--284, 2006.

Digital Library

[14]

M. Prior-Jones. Satellite Communications Systems Buyer's Guide. British Antarctic Survey, 2008.

[15]

J. F. Srour and D. Newton. Freight-specific data derived from intelligent transportation systems: Potential uses in planning freight improvement projects. Transportation Research Record, 1957:66--74, 2006.

[16]

G. Trajcevski, H. Cao, P. Scheuermanny, O. Wolfsonz, and D. Vaccaro. On-line data reduction and the quality of history in moving objects databases. In Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, MobiDE '06, pages 19--26, New York, NY, USA, 2006. ACM.

Digital Library

[17]

P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75--84, Washington, DC, USA, 1975. IEEE Computer Society.

Digital Library

[18]

Y. Zheng, Q. Li, Y. Chen, X. Xie, and W.-Y. Ma. Understanding mobility based on gps data. In Proceedings of the 10th international conference on Ubiquitous computing, UbiComp '08, pages 312--321, New York, NY, USA, 2008. ACM.

Digital Library

[19]

Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from gps trajectories. In Proceedings of the 18th international conference on World wide web, WWW '09, pages 791--800, New York, NY, USA, 2009. ACM.

Digital Library

[20]

H. Zhu, J. Su, and O. H. Ibarra. Trajectory queries and octagons in moving object databases. ACM Press, 2002.

Digital Library

Cited By

Yonekura HOzeki RRizk HYamaguchi H(2024)Restoring Super-High Resolution GPS Mobility DataProceedings of the 2nd ACM SIGSPATIAL International Workshop on Geo-Privacy and Data Utility for Smart Societies10.1145/3681768.3698501(19-24)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681768.3698501
Zhuo WLi SHe TLiu MChan SHa SLee C(2024)Online Path Description Learning Based on IMU Signals From IoT DevicesIEEE Transactions on Mobile Computing10.1109/TMC.2024.340643623:12(11889-11906)Online publication date: Dec-2024
https://doi.org/10.1109/TMC.2024.3406436
Gao YFang ZXu JGong SShen CChen L(2024)An Efficient and Distributed Framework for Real-Time Trajectory Stream ClusteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3312319(1-17)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3312319
Show More Cited By

Index Terms

SQUISH: an online approach for GPS trajectory compression
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

Algorithms for compressing GPS trajectory data: an empirical evaluation
GIS '10: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems

The massive volumes of trajectory data generated by inexpensive GPS devices have led to difficulties in processing, querying, transmitting and storing such data. To overcome these difficulties, a number of algorithms for compressing trajectory data have ...
Sigma encoded inverted files
CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management

Compression of term frequency lists and very long document-id lists within an inverted file search engine are examined. Several compression schemes are compared including Elias γ and δ codes, Golomb Encoding, Variable Byte Encoding, and a class of word-...
Compressing GPS data on mobile devices
OTM'06: Proceedings of the 2006 international conference on On the Move to Meaningful Internet Systems: AWeSOMe, CAMS, COMINF, IS, KSinBIT, MIOS-CIAO, MONET - Volume Part II

In context-aware mobile systems, data on past user behaviour or use of a device can give critical information The scale of this data may be large, and it must be quickly searched and retrieved Compression is a powerful tool for both storing and indexing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

COM.Geo '11: Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications

May 2011

292 pages

ISBN:9781450306812

DOI:10.1145/1999320

Conference Chair:
Lindi Liao

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

COM.Geo '11

COM.Geo '11: 2nd International Conference on Computing for Geospatial Research & Application

May 23 - 25, 2011

DC, Washington, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
917
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yonekura HOzeki RRizk HYamaguchi H(2024)Restoring Super-High Resolution GPS Mobility DataProceedings of the 2nd ACM SIGSPATIAL International Workshop on Geo-Privacy and Data Utility for Smart Societies10.1145/3681768.3698501(19-24)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681768.3698501
Zhuo WLi SHe TLiu MChan SHa SLee C(2024)Online Path Description Learning Based on IMU Signals From IoT DevicesIEEE Transactions on Mobile Computing10.1109/TMC.2024.340643623:12(11889-11906)Online publication date: Dec-2024
https://doi.org/10.1109/TMC.2024.3406436
Gao YFang ZXu JGong SShen CChen L(2024)An Efficient and Distributed Framework for Real-Time Trajectory Stream ClusteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3312319(1-17)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3312319
Liu RZhou SYin SShu YLiang M(2024)AIS-Based Vessel Trajectory Compression: A Systematic Review and Software DevelopmentIEEE Open Journal of Vehicular Technology10.1109/OJVT.2024.34436755(1193-1214)Online publication date: 2024
https://doi.org/10.1109/OJVT.2024.3443675
Wang ZLong CCong GJensen C(2024)Collectively Simplifying Trajectories in a Database: A Query Accuracy Driven Approach2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00334(4383-4395)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00334
Liu ZYuan WLiang MZhang MLiu CLiu RLiu J(2024)An online method for ship trajectory compression using AIS dataJournal of Navigation10.1017/S0373463324000171(1-22)Online publication date: 31-May-2024
https://doi.org/10.1017/S0373463324000171
Li YLi HZhang CZhao YYang Z(2024)Incorporation of adaptive compression into a GPU parallel computing framework for analyzing large-scale vessel trajectoriesTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104648163(104648)Online publication date: Jun-2024
https://doi.org/10.1016/j.trc.2024.104648
Leng RFeng CHao CChao PFang J(2024)PaTraS: A Path-Preserving Trajectory Simplification Method for Low-Loss Map MatchingWeb and Big Data10.1007/978-981-97-2387-4_9(127-144)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-981-97-2387-4_9
Rakhmanov AWiseman Y(2023)Compression of GNSS Data with the Aim of Speeding up Communication to Autonomous VehiclesRemote Sensing10.3390/rs1508216515:8(2165)Online publication date: 19-Apr-2023
https://doi.org/10.3390/rs15082165
Reyes GEstrada VTolozano-Benites RMaquilón V(2023)Batch Simplification Algorithm for Trajectories over Road NetworksISPRS International Journal of Geo-Information10.3390/ijgi1210039912:10(399)Online publication date: 30-Sep-2023
https://doi.org/10.3390/ijgi12100399
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents