Frequent Substring Trees

Implementation and evaluation material for the BTW paper on Frequent Substring Trees (FST). FST supplies substring candidates for the symbol-table search used by FST-OptFSST and Hot/Cold-512. The in-tree OptFSST trainer is a reimplementation with its own pruning rule; the evaluation also includes official OptFSST as a separate comparison.

The repository includes all inputs, benchmark dependencies, raw observations and generated paper tables. Run the commands below from the repository root.

src/                    Codec implementation, command-line tool and tests
lib/fsst/               FSST sources used by the implementation
benchmarks/             Benchmark programs, runners, validators and protocol
  datasets/             All 89 input fields, input manifests and scope
  results/              Paper measurements, provenance and generated tables
third_party/            Stock FSST, official OptFSST, OnPair and Boost
scripts/                Input verification and paper-table generation

lib/fsst/ is the locally adapted implementation basis, including encoding with dynamic programming. third_party/stock_fsst/ contains the unmodified Stock FSST comparison reference, which the benchmark builds separately.

Reproduction

Verify the paper measurements

With Docker installed:

./review.sh

This checks file hashes, the measured codec source fingerprint, all 89 input fields, Python regression tests, all 30,260 raw observations, reconstructed summary tables and 7,120 deterministic comparisons between the two campaigns. It also regenerates the paper and supporting tables and compares their bytes with the included copies. The JSON report is review-output/review-report.json; failed checks return a nonzero exit status.

The container runs with networking disabled and the repository read-only. The first image build needs network access for its base image and system packages. Benchmark inputs and dependency sources are already included. Add compiled C++ correctness tests and synthetic benchmark smokes with:

./review.sh --build-smoke

Build and smoke logs are kept under review-output/build-smoke/. Smoke timings are correctness diagnostics; new performance measurements use the separate measurement procedure below.

Python 3.10 or newer can run the same archive verification directly:

python3 scripts/verify_release.py --output-dir review-output

The native command also accepts --build-smoke when the C++ toolchain described below is installed.

Inspect and regenerate the paper results

The paper uses only the two separately measured campaigns from 29 September 2026:

• benchmarks/results/main/: 19,580 observations covering nine codecs, discrete search budgets and a Stock compiler control.
• benchmarks/results/controls/: 10,680 observations covering matched initialization and Hot/Cold component controls.
• benchmarks/results/paper/: the twelve CSV tables and numeric LaTeX macros used by the manuscript, with provenance.
• benchmarks/results/analysis/: supporting numerical analyses.

These individual checks need only Python; they do not compile code or download data:

python3 scripts/verify_datasets.py
python3 -m unittest discover -s benchmarks/tests -p 'test_*.py' -v
python3 benchmarks/validate_controls.py benchmarks/results/controls --read-only
python3 benchmarks/validate.py benchmarks/results/main \
  --canonical-controls-archive benchmarks/results/controls --read-only
python3 scripts/generate_evaluation.py \
  --output-dir review-output/paper --analysis-dir review-output/analysis
diff -r benchmarks/results/paper review-output/paper
diff -r benchmarks/results/analysis review-output/analysis

--read-only preserves the archived derived files. The exporter checks the included codec sources against their measured content fingerprint, validates input hashes and complete matrices, and recomputes aggregates and paired comparisons. It retains all observations; timing comparisons stay within their own campaign. benchmarks/results/sources.json maps the evidence to local files. The full measurement and aggregation rules are in benchmarks/PROTOCOL.md.

Build and test

The core library and command-line tool need CMake and a C++17 compiler. Python enables the command-line regression tests. No external build dependency is needed for the core:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j4
ctest --test-dir build --output-on-failure

CMake option	Default	Purpose
FST_SINGLE_THREADED_TRAINING	OFF	Run independent training starts sequentially
FST_NATIVE_ARCH	OFF	Enable -march=native for a local performance build
FST_ENABLE_SANITIZERS	OFF	Enable AddressSanitizer and UndefinedBehaviorSanitizer

Debug builds retain debug optimization settings. The tests cover codecs, candidate finding, the command-line tool and controlled search budgets.

The full benchmark needs CMake 3.21 or newer, a C++20-capable GCC/Clang compiler, and Python 3.10 or newer. Install Ninja for --build-smoke; manual builds can also use Make. The default dependency paths use the bundled sources in third_party/, including the hash-pinned Boost archive; configuration and building work offline.

cmake -S benchmarks -B build-benchmark -DCMAKE_BUILD_TYPE=Release \
  -DBTW_CANONICAL_BUILD=OFF
cmake --build build-benchmark -j4
ctest --test-dir build-benchmark --output-on-failure
python3 benchmarks/smoke_controls.py --benchmark build-benchmark/fst_benchmark \
  --output review-output/controls-smoke.json
cmake -S benchmarks -B build-stock-o3 -DCMAKE_BUILD_TYPE=Release \
  -DBTW_CANONICAL_BUILD=OFF -DBTW_STOCK_AVX512_OPTIMIZATION=O3
cmake --build build-stock-o3 -j4
python3 benchmarks/smoke.py --benchmark build-benchmark/fst_benchmark \
  --search-benchmark build-benchmark/fst_search_budget \
  --stock-o3-benchmark build-stock-o3/fst_benchmark \
  --output review-output/main-smoke.json

The independent Stock-O3 build changes only the Stock AVX-512 translation unit's optimization level. Its stored sizes and checksums must match the primary Stock build. Smoke reports require fresh output filenames.

Collect new performance measurements

Use a Linux workstation/server CPU with affinity support. Select a free logical CPU and keep its SMT sibling idle. Inspect load, frequency settings and thermal state, allow build load to subside, and record interruptions. The runners check source contents, inputs and binaries, prepare separate builds, run correctness checks, and execute one benchmark process at a time.

Replace FREE_LOGICAL_CPU with the selected CPU number and choose unique labels:

python3 benchmarks/run_controls.py --cpu FREE_LOGICAL_CPU --label reproduction-controls
python3 benchmarks/run.py --cpu FREE_LOGICAL_CPU --label reproduction-main \
  --controls-archive benchmarks/results/controls

Both campaigns use all 89 fields and ten seeds. Controls produce 10,680 observations; main produces 19,580 across codecs, search budgets and the compiler control. The main runner compares deterministic sizes, samples, checksums and decisions against the included paper controls. Each new campaign records its own CPU, compiler and timings.

The default build paths are build-controls, build-benchmark and build-stock-o3. Results go under benchmarks/results/reruns/<label>. Use a new label for each independent run. Add --resume only when source, binaries, inputs and host state are unchanged; retain partial files and logs.

Inputs and optional re-extraction

benchmarks/datasets/ contains DBText-23 under dbtext/ and Native-66 under native/derived/. Verification checks file bytes, logical sizes and row counts against the measurement manifests. The Native extraction manifest records 69 columns; three columns exceed the 16-MiB input scope and are excluded. This is a benchmark selection, not a codec limit.

The included inputs suffice for verification and new measurements. Independent re-extraction is optional and needs DuckDB 1.4.3, network access to the original datasets and a separate scratch directory:

python3 scripts/prepare_corpora.py plan --data-dir /path/to/native-scratch
python3 scripts/prepare_corpora.py download --data-dir /path/to/native-scratch
python3 scripts/prepare_corpora.py extract --data-dir /path/to/native-scratch --label reproduction
python3 scripts/prepare_corpora.py verify --data-dir /path/to/native-scratch --label reproduction

Alternate extraction manifests require their independently verified SHA-256 through --native-manifest-sha256. The same field-content and scope checks apply. Source specifications and the extraction recipe are included alongside the data in benchmarks/datasets/.

Table construction

The multi-start trainer uses five deterministic training sample streams and two validation samples. Each sample targets 16 KiB and retains value boundaries. Inputs within the sample budget are used in full, so their samples coincide; larger samples can also overlap. The first start uses an empty table. The other four starts use 64, 128, 255 and 64 FST candidates from their training samples.

Every start performs five OptFSST refinement rounds. Dynamic programming parses chunks of at most 511 bytes, counts symbols and adjacent pairs and triples, and rebuilds the table. The two tables with the lowest validation estimates are compared on the complete input, including serialized table size.

The matched no-FST multi-start control shares the five samples, terminator, refinement rounds, validation samples and final comparison, but initializes each start with an empty table. The single-start pair shares one primary sample and differs only in empty versus FST initialization. Sample checksums and search counts verify these comparisons. FST counting is included in training cost. Both single-start controls also include one exact full-input size pass for diagnostics. These controls test fixed search budgets.

Hot/Cold trains its own FST-OptFSST base and forms additional two- through eight-byte symbols from adjacent parse tokens. Tier-aware parsing assigns frequent symbols to 254 one-byte Hot slots and 256 two-byte Cold slots. One-byte symbols are omitted from the Cold tier because a literal has the same cost.

Command-line tool and library

./build/fst_optfsst --sample-seed 127 input.txt output.fsst
./build/fst_optfsst --hotcold512 --sample-seed 127 input.txt output.fhc
./build/fst_optfsst -d output.fsst restored.txt

The tool processes independent blocks of at most 4 MiB. Decompression detects ordinary FSST and Hot/Cold blocks automatically. Input and output must name different files.

FSST-compatible entry points are in src/fsst/fst_optfsst.h; the shared C++ adapter and controlled training API are in src/fsst/codec_adapter.h. The bundled FSST sources retain their upstream MIT license and attribution in lib/fsst/LICENSE. Benchmark dependency licenses are included in third_party/.