Benchmarking suffix trees

Methodology

Explored dimensions:

• suffix tree implementations
• test cases
• methods (LCA, Letter, SLink, Child, SDepth, Parent)

Directory structure

• bin: Contains the executables of the project.
• indexes: Contains the serialized suffix trees.
• results: Contains the results of the experiments.
• src: Contains the source code of the benchmark.
• stats: Contains statistics about the construction and the structure of the indexes.
• visualize: Contains a R-script which generates a report in LaTeX format.

Prerequisites

• For the visualization you need the following software:
  • R to generate the tex files.
  • pdflatex to generate the pdf reports.

Usage

• make timing compiles the programs, downloads the test instances, builds the suffix trees, runs the performance tests and generates a report located at visualize/suffix_trees.pdf. The raw numbers of the timings can be found in the results/all.txt file.
• All created binaries and test results can be deleted by calling make cleanall.

Customization of the benchmark

The project contains several configuration files:

• index.config: Specify different suffix tree implementations.
• test_case.config: Specify test instances by ID, path, LaTeX-name for the report, and download URL.
• compile_options.config: Specify compile options by option string.

Note that the benchmark will execute every combination of suffix trees and test cases.