You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
We present a method for compressing trajectories in an unsupervised manner. Given a set of trajectories sampled from a space we construct a basis for compression whose elements correspond to paths in the space which are topologically distinct. This is achieved by computing a canonical representative for each element in a generating set for the first homology group and decomposing these representatives into a set of distinct paths. Trajectory compression is subsequently accomplished through representation in terms of this basis. Robustness with respect to outliers is achieved by only considering those elements of the first homology group which exist in the super-level sets of the Kernel Density Estimation (KDE) above a threshold. Robustness with respect to small scale topological artifacts is achieved by only considering those elements of the first homology group which exist for a sufficient range in the super-level sets. We demonstrate this approach to trajectory compression in the context of a large set of crowd-sourced GPS trajectories captured in the city of Chicago. On this set, the compression method achieves a mean geometrical accuracy of 108 meters with a compression ratio of over 12.
[1] S. Bhattacharya, M. Likhachev, and V. Kumar, “Topological constraints in search-based robot path planning,” Autonomous Robots, vol. 33, no. 3, pp. 273-290, 2012.
[2] M. Kuderer, C. Sprunk, H. Kretzschmar, and W. Burgard, “Online generation of homotopically distinct navigation paths,” in IEEE International Conference on Robotics and Automation, 2014, pp. 6462- 6467.
[3] F. T. Pokorny and D. Kragic, “Data-driven topological motion planning with persistent cohomology,” in Robotics: Science and Systems Conference, 2015.
[4] W. Liu, Y. Zheng, S. Chawla, J. Yuan, and X. Xing, “Discovering spatio-temporal causal interactions in traffic data streams,” in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2011, pp. 1010-1018.
[5] H. Pham, C. Shahabi, and Y. Liu, “Ebm: an entropy-based model to infer social strength from spatiotemporal data,” in Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 2013, pp. 265-276.
[6] M. De Berg, M. Van Kreveld, M. Overmars, and O. C. Schwarzkopf, Computational geometry. Springer, 2000.
[7] R. Song, W. Sun, B. Zheng, and Y. Zheng, “Press: A novel framework of trajectory compression in road networks,” Proceedings of the VLDB Endowment, vol. 7, no. 9, pp. 661-672, 2014.
[8] K. Liu, Y. Li, J. Dai, S. Shang, and K. Zheng, “Compressing large scale urban trajectory data,” in Proceedings of the Fourth International Workshop on Cloud Data and Platforms, 2014, p. 3.
[9] G. Kellaris, N. Pelekis, and Y. Theodoridis, “Map-matched trajectory compression,” Journal of Systems and Software, vol. 86, no. 6, pp. 1566-1579, 2013.
[11] R. Ghrist, “Barcodes: the persistent topology of data,” Bulletin of the American Mathematical Society, vol. 45, no. 1, pp. 61-75, 2008.
[12] H. Edelsbrunner and J. Harer, Computational topology: an introduction. American Mathematical Soc., 2010.
[13] A. Zomorodian and G. Carlsson, “Localized homology,” Computational Geometry, vol. 41, no. 3, pp. 126-148, 2008.
[14] J. M. Phillips, B. Wang, and Y. Zheng, “Geometric inference on kernel density estimates,” arXiv preprint arXiv:1307.7760, 2013.
[15] F. Chazal, B. T. Fasy, F. Lecci, B. Michel, A. Rinaldo, and L. Wasserman, “Robust topological inference: Distance to a measure and kernel distance,” arXiv preprint arXiv:1412.7197, 2014.
[18] N. Meratnia and A. Rolf, “Spatiotemporal compression techniques for moving point objects,” in Advances in Database Technology-EDBT 2004. Springer, 2004, pp. 765-782.
[19] Y. Chen, K. Jiang, Y. Zheng, C. Li, and N. Yu, “Trajectory simplification method for location-based social networking services,” in Proceedings of the 2009 International Workshop on Location Based Social Networks. ACM, 2009, pp. 33-40.
[20] D. Feldman, C. Sung, and D. Rus, “The single pixel gps: learning big data signals from tiny coresets,” in Proceedings of the 20th International Conference on Advances in Geographic Information Systems. ACM, 2012, pp. 23-32.
[21] O. Salzman, D. Shaharabani, P. K. Agarwal, and D. Halperin, “Sparsification of motion-planning roadmaps by edge contraction,” The International Journal of Robotics Research, p. 0278364914556517, 2014.
[22] J. Muckell, J.-H. Hwang, C. T. Lawson, and 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. ACM, 2010, pp. 402- 405.
[23] C. E. White, D. Bernstein, and A. L. Kornhauser, “Some map matching algorithms for personal navigation assistants,” Transportation Research Part C: Emerging Technologies, vol. 8, no. 1, pp. 91-108, 2000.
[24] P. Newson and J. Krumm, “Hidden markov map matching through noise and sparseness,” in Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. ACM, 2009, pp. 336-343.
[25] S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk, “On map-matching vehicle tracking data,” in Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 2005, pp. 853-864.
[26] B. W. Silverman, Density estimation for statistics and data analysis. CRC press, 1986, vol. 26.
[27] F. Chazal, D. Cohen-Steiner, and Q. Me´rigot, “Geometric inference for probability measures,” Foundations of Computational Mathematics, vol. 11, no. 6, pp. 733-751, 2011.
[32] A. Zomorodian, “Computational topology,” in Algorithms and theory of computation handbook. Chapman & Hall/CRC, 2010, pp. 3-3.
[33] S. Kim, K. Sreenath, S. Bhattacharya, and V. Kumar, “Optimal trajectory generation under homology class constraints,” in IEEE Conference on Decision and Control, 2012, pp. 3157-3164.
[34] C. Chen and M. Kerber, “Persistent homology computation with a twist,” in Proceedings 27th European Workshop on Computational Geometry. Citeseer, 2011.
[35] A. Zomorodian and G. Carlsson, “Computing persistent homology,” Discrete & Computational Geometry, vol. 33, no. 2, pp. 249-274, 2005.
[36] H. Edelsbrunner and A. Zomorodian, “Computing linking numbers of a filtration,” in Algorithms in Bioinformatics. Springer, 2001, pp. 112-127.
[37] H. Edelsbrunner and J. Harer, “Persistent homology - a survey,” in Surveys on Discrete and Computational Geometry. Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, Eds. American Mathematical Society, 2008.
[38] M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk, “A comparison and evaluation of map construction algorithms using vehicle tracking data,” GeoInformatica, pp. 1-32, 2014.
[39] T. J. Steiner, G. Huang, and J. J. Leonard, “Location utility-based map reduction,” in IEEE International Conference on Robotics and Automation, 2015, pp. 479-486.