MPHF-Experiments

Comparison of a wide range different minimal perfect hash functions (MPHFs). From these, it can generate comprehensive plots like Pareto plots, and simple comparison tables used in several papers.

The framework provides a unified interface to test basically all modern MPHF constructions that are currently available, including:

• Bucket Placement
  • CHD (Paper, Code)
  • PHOBIC (Paper, Code)
  • FCH (Paper, Code)
  • FCH (Re-Implementation by Pibiri) (Code)
  • PHOBIC-GPU (Paper, Code)
  • PTHash (Paper, Code)
  • PTHash-HEM (Paper, Code)
  • PHast (Not published yet) (Code)
  • PtrHash (Paper, Code)
• Consensus
  • Consensus-RS (Paper, Code)
• Fingerprinting
  • BBHash (Paper, Code)
  • FiPS (Paper, Code)
  • FMPH (Paper, Code)
  • FMPH-GO (Paper, Code)
• RecSplit
  • RecSplit (Paper, Code)
  • GpuRecSplit (Paper, Code)
  • SIMDRecSplit, RecSplit with rotation fitting (Paper, Code)
• Retrieval
  • BDZ / BPZ (Paper, Code)
  • BMZ (Paper, Code)
  • CHM (Paper, Code)
  • WBPM (Paper, Code)
  • SicHash (Paper, Code)
• ShockHash
  • ShockHash (+ SIMD version) (Paper, Code)
  • Bipartite ShockHash (Paper, Code)
  • Bipartite ShockHash-Flat (Paper, Code)
  • MorphisHash (Paper, Code)
  • MorphisHash-Flat (Paper, Code)

Cloning the Repository

This repository contains submodules. To clone the repository including submodules, use the following command.

git clone --recursive https://github.com/ByteHamster/MPHF-Experiments.git

Running the Experiments Directly

Compiling works like with every cmake project.

cmake -B ./build -DCMAKE_BUILD_TYPE=Release cmake --build ./build -j

This might take about 5-15 minutes because of the large number of competitors. You can then run one of the benchmarks, for example ./build/TablePtrHash --help or ./build/Comparison --help.

Code Structure

The main comparison code can be found in the src directory. This includes tabular comparisons like they are used in different papers, as well as the more general Pareto plot in src/Comparison.cpp. To add a new competitor to the framework, have a look at the contenders directory. For each contender, there are two files. (1) A general wrapper header class that unifies the interface of the competitor, and (2) a cpp file that tests a wide range of configurations for the general Pareto plot. The cpp file should contain all meaningful configurations to cover all possible trade-offs. After adding a contender, make sure to re-run cmake. If you want to add a new comparison table, make sure to also adapt the CMakeLists.txt file accordingly.

Running the Experiments with Docker

For easier reproducibility and less setup overhead, we provide a docker image to run the experiments. However, for the measurements in the papers, we run the code directly and with more data points. We refer to Docker.md for details on how to use this repository with Docker.

License

This code is licensed under the GPLv3.