Document Open Access Logo

Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance

Authors Karl Bringmann, Marvin Künnemann, André Nusser

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.17.pdf
  • Filesize: 1.27 MB
  • 21 pages

Document Identifiers

Author Details

Karl Bringmann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Marvin Künnemann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
André Nusser
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
  • Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus, Germany

Cite AsGet BibTex

Karl Bringmann, Marvin Künnemann, and André Nusser. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.17

Abstract

The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fréchet distance, in particular for realistic input curves, are highly desirable. This has even lead to a designated competition, the ACM SIGSPATIAL GIS Cup 2017: Here, the challenge was to implement a near-neighbor data structure under the Fréchet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fréchet distance. In this work, we present a fast, certifying implementation for deciding the Fréchet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve the state of the art for the GIS Cup challenge. We experimentally evaluate our implementation on a large benchmark consisting of several data sets (including handwritten characters and GPS trajectories). Compared to the winning implementation of the GIS Cup, we obtain running time improvements of up to more than two orders of magnitude for the decision procedure and of up to a factor of 30 for queries to the near-neighbor data structure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • curve simplification
  • Fréchet distance
  • algorithm engineering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. Computing the Discrete Fréchet Distance in Subquadratic Time. SIAM J. Comput., 43(2):429-449, 2014. URL: http://dx.doi.org/10.1137/130920526.
  2. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry &Applications, 5(01n02):75-91, 1995. Google Scholar
  3. Microsoft Research Asia. GeoLife GPS Trajectories. https://www.microsoft.com/en-us/download/details.aspx?id=52367. Accessed: 2018-12-03.
  4. Maria Astefanoaei, Paul Cesaretti, Panagiota Katsikouli, Mayank Goswami, and Rik Sarkar. Multi-resolution sketches and locality sensitive hashing for fast trajectory processing. In Proc. 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2018. Google Scholar
  5. Julian Baldus and Karl Bringmann. A Fast Implementation of Near Neighbors Queries for Fréchet Distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL'17, pages 99:1-99:4, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3139958.3140062.
  6. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 661-670. IEEE, 2014. Google Scholar
  7. Karl Bringmann and Marvin Künnemann. Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. Int. J. Comput. Geometry Appl., 27(1-2):85-120, 2017. URL: http://dx.doi.org/10.1142/S0218195917600056.
  8. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. Journal of Computational Geometry, 7(2):46-76, December 2015. URL: http://dx.doi.org/10.20382/jocg.v7i2a4.
  9. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance. Discrete & Computational Geometry, 58(1):180-216, 2017. URL: http://dx.doi.org/10.1007/s00454-017-9878-7.
  10. Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fréchet distance. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 645-654. Society for Industrial and Applied Mathematics, 2009. Google Scholar
  11. Kevin Buchin, Yago Diez, Tom van Diggelen, and Wouter Meulemans. Efficient Trajectory Queries Under the Fréchet Distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL'17, pages 101:1-101:4, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3139958.3140064.
  12. Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, and Maarten Löffler. Approximating (k, 𝓁)-center clustering for curves. CoRR, abs/1805.01547, 2018. URL: http://arxiv.org/abs/1805.01547.
  13. Jonathan Campbell, Jonathan Tremblay, and Clark Verbrugge. Clustering Player Paths. In FDG, 2015. Google Scholar
  14. Matteo Ceccarello, Anne Driemel, and Francesco Silvestri. FRESH: Fréchet similarity with hashing. CoRR, abs/1809.02350, 2018. URL: http://arxiv.org/abs/1809.02350.
  15. Erin Chambers, Brittany Terese Fasy, Yusu Wang, and Carola Wenk. Map-matching using shortest paths. In Proceedings of the 3rd International Workshop on Interactive and Spatial Computing, pages 44-51. ACM, 2018. Google Scholar
  16. Daniel Chen, Anne Driemel, Leonidas J Guibas, Andy Nguyen, and Carola Wenk. Approximate map matching with respect to the Fréchet distance. In 2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 75-83. SIAM, 2011. Google Scholar
  17. Dua Dheeru and Efi Karra Taniskidou. UCI machine learning repository, 2017. URL: http://archive.ics.uci.edu/ml.
  18. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet Distance for Realistic Curves in Near Linear Time. Discrete & Computational Geometry, 48(1):94-127, July 2012. URL: http://dx.doi.org/10.1007/s00454-012-9402-z.
  19. Fabian Dütsch and Jan Vahrenhold. A Filter-and-Refinement-Algorithm for Range Queries Based on the Fréchet Distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL'17, pages 100:1-100:4, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3139958.3140063.
  20. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. Google Scholar
  21. M Maurice Fréchet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo (1884-1940), 22(1):1-72, 1906. Google Scholar
  22. Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119-161, 2011. Google Scholar
  23. Hong Wei, Riccardo Fellegara, Yin Wang, Leila De Floriani, and Hanan Samet. Multi-level Filtering to Retrieve Similar Trajectories Under the Fréchet Distance. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '18, pages 600-603, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3274895.3274978.
  24. Martin Werner. ACM SIGSPATIAL GIS Cup 2017 Data Set. https://www.martinwerner.de/datasets/san-francisco-shortest-path.html. Accessed: 2018-12-03.
  25. Martin Werner and Dev Oliver. ACM SIGSPATIAL GIS Cup 2017 - Range Queries Under Fréchet Distance. ACM SIGSPATIAL Newsletter, To Appear., 2018. Google Scholar
  26. Ben H Williams. Character Trajectories Data Set. https://archive.ics.uci.edu/ml/datasets/Character+Trajectories. Accessed: 2018-12-03.
  27. Tim Wylie and Binhai Zhu. Intermittent Map Matching with the Discrete Fréchet Distance. arXiv preprint, 2014. URL: http://arxiv.org/abs/1409.2456.
  28. Jianbin Zheng, Xiaolei Gao, Enqi Zhan, and Zhangcan Huang. Algorithm of On-Line Handwriting Signature Verification Based on Discrete Fréchet Distance. In Lishan Kang, Zhihua Cai, Xuesong Yan, and Yong Liu, editors, Advances in Computation and Intelligence, pages 461-469, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  29. Yu Zheng, Xing Xie, and Wei-Ying Ma. Understanding Mobility Based on GPS Data. In Proceedings of the 10th ACM conference on Ubiquitous Computing (Ubicomp 2008), September 2008. URL: https://www.microsoft.com/en-us/research/publication/understanding-mobility-based-on-gps-data/.
  30. Yu Zheng, Xing Xie, and Wei-Ying Ma. Mining Interesting Locations and Travel Sequences From GPS Trajectories. In Proceedings of International conference on World Wide Web 2009, April 2009. WWW 2009. URL: https://www.microsoft.com/en-us/research/publication/mining-interesting-locations-and-travel-sequences-from-gps-trajectories/.
  31. Yu Zheng, Xing Xie, and Wei-Ying Ma. GeoLife: A Collaborative Social Networking Service among User, location and trajectory. IEEE Data(base) Engineering Bulletin, June 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact