Fast Discrete Fréchet Distance

This is a collection of different C++ implementations for calculating the discrete Fréchet distance between two polygonal curves:

1. vanilla: A recursion-free adaptation of the original algorithm as proposed in Computing Discrete Fréchet Distance by T. Eiter and H. Mannila (1994), used as a baseline.
2. linear: This formulation reduces the quadratic memory footprint to a linear one.
3. SIMD: Formulation using SIMD parallelization on a single CPU core.
4. CUDA: Formulation using CUDA.

Implementations of all these variants can be found under ffrechet-{vanilla,linear,simd,cuda}/source/ or by simply clicking on the listed names above.

Toolchain Requirements ⚙️

This project has been primarily tested on Linux environments. Please note the following dependencies:

1. SIMD implementation: Requires at least GCC-11, as it relies on the experimental SIMD implementation of the Parallelism Technical Specification (TS) v2.
2. CUDA implementation: Requires a compiler version compatible with the NVCC installation.

You can customize the compiler versions by editing the respective toolchain files ffrechet-simd/ffrechet-simd_toolchain.cmake and ffrechet-simd/ffrechet-cuda_toolchain.cmake.

Installation 🛠️

First, make sure that you have checked out the dependencies (google-benchmark and google-test) by running

$ git submodule init
$ git submodule update

Then, you can customize the build options in CMakeUserPresets.json or simply copy the default one from CMakeUserPresets.json.EXAMPLE:

$ cp CMakeUserPresets.json.EXAMPLE CMakeUserPresets.json

Finally, configure and build the entire project via

$ cmake --preset=release
$ cmake --build --preset=release

If you want to run the benchmark, type:

$ ./build/release/install/bin/ffrechet-benchmark \
--benchmark_out_format=json \
--benchmark_out=benchmark.json

this will run the benchmark and store the results in benchmark.json. Remember to enable the performance mode on your CPU before running the benchmark, e.g., via

$ sudo cpupower frequency-set --governor performance

Afterwards, you can reset the performance mode back to powersave via

$ sudo cpupower frequency-set --governor powersave

Developer Mode 👷

In case you are interested in contributing to this project, you might find our debug preset helpful:

$ cmake --preset=debug
$ cmake --build --preset=debug

You can test your changes by running

$ ./build/debug/install/bin/ffrechet-test

Please make sure to obey the formatting, for example by running

$ cmake --build --preset=debug -t format-check
$ cmake --build --preset=debug -t format-fix

Benchmark results and other visualizations 🎨

We use Jupyter Notebooks to render the visualizations of the results of the benchmarks. You can find them here alongside others.

Python Implementations 🐍

Python implementations of the discrete Fréchet Distance can be found here.