Walking your frog fast in 4 LoC ... or more
The Fréchet distance, a widely used metric for measuring trajectory similarity, presents challenges in implementation due to its complexity and inefficiency for generic point distance measures. Therefore, this metric is often only approximated in terms of a dynamic programming problem in practice that, in theory, circumvent some of these limitations. This talk explores a journey starting with a 1994 algorithm - rooted in recursion and branches with a quadratic memory footprint - and transforms it for modern hardware efficiency. We delve into various iterations, fiddling with profilers, hit some pitfalls of the STL, break Conor Hoekstra's heart, and eventually (super)build an efficient algorithm in modern C++ that uses SIMD and can even run on GPGPUs that unveils how to walk your frog fast.
Nis Meinert
Nis is a physicist working as a team lead of a small working group at the Institute of Communications and Navigation at the German Aerospace Center (DLR) in Germany. His team develops fast and robust algorithms to analyze large maritime radar and AIS data sets, employing both traditional and cutting-edge ML/AI techniques. Nis holds a Ph.D. for conducting research on rare baryonic decays using data from a CERN experiment. Before joining DLR, Nis worked for Pasteur Labs, where he focused on developing Physics Informed Neural Networks and other Neural Network-based surrogates to accelerate CFD simulations.
Nis has strong feelings for contemporary C++, he codes in Python when necessary, ponders about SIMD and clean APIs when possible, and has secretly fallen in love with APL. You typically find him with a cup of coffee in front of one of his many mechanical keyboards, diligently navigating the intricacies of yak shaving.