Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


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.


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.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Corcoran, Padraig; Mooney, Peter; Huang, Guoquan (2016)
Languages: English
Types: Unknown
Subjects: QA75
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [10] F. Schmid, K.-F. Richter, and P. Laube, “Semantic trajectory compression,” in Advances in Spatial and Temporal Databases. Springer, 2009, pp. 411-416.
    • [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.
    • [16] H. Edelsbrunner, D. Letscher, and A. Zomorodian, “Topological persistence and simplification,” Discrete and Computational Geometry, vol. 28, no. 4, pp. 511-533, 2002.
    • [17] P. Corcoran, P. Mooney, and A. Winstanley, “Planar and non-planar topologically consistent vector map simplification,” International Journal of Geographical Information Science, vol. 25, no. 10, pp. 1659- 1680, 2011.
    • [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.
    • [28] R. Ghrist, Elementary applied topology. CreateSpace Independent Publishing Platform, 2014.
    • [29] A. Hatcher, Algebraic Topology. Cambridge University Press, 2002.
    • [30] J. Lee, Introduction to topological manifolds. Springer Science & Business Media, 2010, vol. 940.
    • [31] F. T. Pokorny, M. Hawasly, and S. Ramamoorthy, “Multiscale topological trajectory classification with persistent homology,” in Robotics: science and systems, 2014.
    • [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.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article