Data

Tools

Indexes

Applications

Experiments

Open Source Science

fast_frechet

Comparison of different (fast) discrete Fréchet distance implementations in C++ and CUDA.

https://github.com/avitase/fast_frechet

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ✓
    Academic publication links
    Links to: arxiv.org
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (11.9%) to scientific vocabulary

Keywords

benchmark cpp cuda frechet-distance simd
Last synced: 6 months ago · JSON representation ·

Repository

Comparison of different (fast) discrete Fréchet distance implementations in C++ and CUDA.

Basic Info
Statistics
  • Stars: 2
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Topics
benchmark cpp cuda frechet-distance simd
Created about 2 years ago · Last pushed 7 months ago
Metadata Files
Readme License Citation

README.md

Fast Discrete Fréchet Distance

arXiv

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 bash $ 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: bash $ cp CMakeUserPresets.json.EXAMPLE CMakeUserPresets.json

Finally, configure and build the entire project via bash $ cmake --preset=release $ cmake --build --preset=release

If you want to run the benchmark, type: bash $ ./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 bash $ sudo cpupower frequency-set --governor performance

Afterwards, you can reset the performance mode back to powersave via bash $ 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: bash $ cmake --preset=debug $ cmake --build --preset=debug

You can test your changes by running

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

Please make sure to obey the formatting, for example by running bash $ 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.

Owner

  • Name: Nis Meinert
  • Login: avitase
  • Kind: user
  • Company: Pasteur Labs

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Meinert"
  given-names: "Nis"
  orcid: "https://orcid.org/0000-0002-4712-9579"
title: "Fast Discrete Fréchet Distance"
version: 1.5
date-released: 2023-09-24
url: "https://github.com/avitase/fast_frechet"

GitHub Events

Total
  • Watch event: 1
  • Push event: 1
  • Fork event: 1
Last Year
  • Watch event: 1
  • Push event: 1
  • Fork event: 1

Issues and Pull Requests

Last synced: 11 months ago

All Time
  • Total issues: 0
  • Total pull requests: 5
  • Average time to close issues: N/A
  • Average time to close pull requests: 4 minutes
  • Total issue authors: 0
  • Total pull request authors: 1
  • Average comments per issue: 0
  • Average comments per pull request: 0.0
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 0
  • Pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Issue authors: 0
  • Pull request authors: 0
  • Average comments per issue: 0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
Pull Request Authors
  • avitase (9)
Top Labels
Issue Labels
Pull Request Labels

Dependencies

.github/workflows/ci.yml actions
  • actions/checkout v4 composite
viz/requirements.txt pypi
  • matplotlib ==3.8.2
  • pandas ==2.2.0
  • pyarrow ==15.0.0