Skip to content

benchmarking.md

Latest commit

 

History

History
210 lines (174 loc) · 15.8 KB

benchmarking.md

File metadata and controls

210 lines (174 loc) · 15.8 KB
Raw

Benchmarking: datasets, comparability, and findings

How we measure clustering quality and speed, against which datasets and engines, and the caveats that make a comparison fair. Pairs with tools/README.md (how to run) and the 1.0.0 benchmark trackers (#53 CPU-speed comparisons, #54 quality harness).

The 1.0.0 reference study — done. The large reproducible matrix that consolidates these benchmarks to pick the library's data-dependent defaults and serve as the single citable comparison has now been run (2026-06-20) — see § 1.0.0 reference benchmark matrix below for the results and decisions. Its design (axes, decisions D1–D5, fairness contract) is in ROADMAP-1.0.0-benchmark-matrix.md and how to re-run it is in benchmark-matrix-runbook.md. The comparability rules below are its fairness contract. The sections after that describe the older ad-hoc benchmarks the matrix subsumes.

Datasets

group what source ground truth?
Franti shape sets Aggregation, Compound, spiral, R15, jain, flame, D31 (2-D) cs.uef.fi/sipu/datasets via tools/fetch_datasets.py → data/franti/ yes
synthetic toys blobs, moons, varied, density (2-D, Euclidean) tools/datasets.py generators yes
cosine blobs clusters along distinct directions, L2-normalized (8-D, 16-D) quality_benchmark.py:make_cosine_blobs yes
RGB pixel clouds color-clustering images data/img_*.csv no (timing only)
  • The Franti sets are third-party data with published results across many papers (the same sets the FOPTICS paper reported on), so scores are comparable beyond this repo. Please cite Franti et al. if you publish results. They are not committed (data/ is gitignored); run tools/fetch_datasets.py to (re)download.
  • Everything talks through the CSV contract in tools/README.md (a coords file x0,x1,… + a label truth file).
  • Cosine blobs exist for sOPTICS. sOPTICS is a cosine method, so it needs direction-based clusters to be evaluated fairly (see below); the Euclidean toys/Franti sets are the wrong metric for it.

Comparability — what makes a comparison fair

These are the things that, if ignored, produce misleading numbers:

  1. Same generating distance (eps) — the big one. OPTICS timing is dominated by neighborhood size, which eps controls. Our harness runs at the library's auto-estimated eps; it emits that eps and passes the identical value to dbscan-R. Skipping this made dbscan-R look ~50× slower on D31 (347 ms vs 7 ms) purely because it used a larger eps and therefore did more work. Always compare at equal eps.
  2. Cross-machine absolute times are not reproducible (hardware differs). The reproducible, comparable quantity is the ratio of engines on the same machine/datasets/params. Use any published numbers to sanity-check your setup, not to match in absolute ms.
  3. Exclude I/O / startup from the timed region on every side; time only the ordering.
  4. Like-for-like extraction. We and dbscan-R both use Xi at the same chi/xi; the OPTICS ordering is the algorithm, the extraction is a separate, parameter-sensitive step.
  5. Tie-breaking differs. We break reachability ties low-index-first; ELKI and mhahsler/dbscan break them high-index-first. So orderings are not bit-identical across engines even when both are exact — compare clusters (ARI/NMI/Rand) and timing, never raw orderings. (An opt-in high-index tie-break would let us match ELKI/dbscan exactly; not implemented.)
  6. Metric must match the method. sOPTICS is cosine; scoring it on Euclidean layouts is a metric mismatch, not a defect. scikit-learn OPTICS(cluster_method="xi") is sensitive to xi and can score low at defaults — it is a reference, not a target.

1.0.0 reference benchmark matrix — results

The single citable reference run (issue #59). Generated by the pipeline in benchmark-matrix-runbook.md (gen_dataset.py → optics_matrix / sk_engine.py → run_matrix.py → analyze_matrix.py); the raw results/matrix.csv and results/report.md are reproducible artifacts (gitignored), so re-run the runbook to regenerate them.

Reference machine (2026-06-20). Intel Core Ultra 7 155H (16C / 22T), 31.5 GB RAM, Windows 11; MSVC 2022, C++20, Release; Python 3.14.5 / scikit-learn 1.9.0 / NumPy 2.4.6; 4 worker threads (OPTICS_BENCH_THREADS=4). Only same-machine ratios are reproducible (rule 2 above); absolute ms are machine-specific. The matrix spans n = 316 … 1e6, d = 1 … 128, and sparse/mixed/dense layouts, across all four of this library's algorithms plus scikit-learn OPTICS / HDBSCAN / k-means.

Headline

  • OPTICS is ~100× faster than scikit-learn OPTICS. Across 23 cells where both ran: median 109×, range 5.9×–714× (20/23 ≥ 10×, 13/23 ≥ 100×). The largest gaps are at mid–high dimension (e.g. ~350× at 1500×16-D). Beyond n ≈ 1e5 scikit-learn OPTICS is too slow to run at all (feasibility-gated out), so the library extends the practical range by orders of magnitude.
  • Our HDBSCAN* matches scikit-learn exactly. |ours − sklearn| ARI over 23 co-run cells: mean 0.0002, max 0.0032 — i.e. bit-for-bit-equivalent clustering, validating the reimplementation.
  • Quality caveat (honest). On the mixed-density Euclidean blobs the ξ extraction is genuinely hard and OPTICS ARI is low — but equally low for ours and scikit-learn (parity holds; it is a dataset-difficulty artifact, not a regression). HDBSCAN handles those far better, and k-means (which is given k) is the quality ceiling there.

Decisions D1–D5 — every one confirms the shipped defaults

# decision result default (confirmed)
D1 backend by dimensionality eps-approx nanoflann gives ~1.5× at d = 8–16 with zero ARI loss, but the gain vanishes by d ≥ 32 (nothing left to prune); HNSW is index-build-bound and 2–11× slower end-to-end at n = 2e4 (its query-time crossover only pays off at much larger n) exact NanoflannBackend
D2 sOPTICS vs OPTICS sOPTICS overtakes exact OPTICS at high d / large n (d ≥ 6 & n ≥ 1e5: 5.8–11.6×; d ≥ 32 & n = 1e4: 3.3–7.4×); exact wins at low d / small n. sOPTICS quality is only comparable to exact on angular/cosine data (metric match) exact OPTICS for low-d Euclidean; sOPTICS for the high-d / large-n / cosine regime
D3 Precompute vs OnDemand where the cache fits (n = 8k, all densities) Precompute is 1.1–2.7× faster; its only loss is the large-n-dense memory wall (O(n·avg_nbrs) buffer → ~19 GB at 100k px, OOM) OnDemand (memory-safe; opt into Precompute when the cache fits)
D4 ε estimator (knee vs uniform) knee wins quality where the cluster scale varies (sparse-16-D: 0.999 vs 0.493) and is never slower (uniform over-estimates the radius → bigger neighborhoods); the lone cell favouring uniform is within seed noise knee (epsilon_estimation_knee, #57)
D5 HDBSCAN* vs sHDBSCAN exact HDBSCAN* (dense-Prim, O(n²)) is feasible only to n ≈ 1e4; at n ≥ 1e5 it is gated out and sHDBSCAN is the only option (14–43 s at n = 1e5) exact HDBSCAN* for small/medium n; sHDBSCAN for n ≥ ~1e5

The upshot for users: the out-of-the-box defaults are the right ones for the common case — exact nanoflann, OnDemand acquisition, the knee ε. Switch to sOPTICS / sHDBSCAN (cosine, approximate) when you are in the high-dimensional or very-large-n regime; switch to Precompute when your cloud is sparse enough that the neighbor cache fits in RAM.

D5 follow-up — the HDBSCAN* MST backbone crossover (#66 / #72)

D5 above measured only dense-Prim vs sHDBSCAN. The exact/near-exact sub-quadratic MST backbones added since (MstAlgorithm::Boruvka, exact; MstAlgorithm::KnnGraph, near-exact — #66) needed their own crossover study to drive the MstAlgorithm::Auto selector (#72). It is a focused engine-selection timing sweep (optics_hdbscan_mst_probe sweep: n×dim grid over the backbones, exact Borůvka as the agreement reference), deliberately not a full matrix axis — it measures our own backbones' relative speed, not cross-library quality.

Reference run (2026-06-21, same machine as above, 4 threads, well-separated blobs):

result Auto policy
dense-Prim never fastest (O(n²)); ties only at n < ~1000 n < 1000 ⇒ DensePrim (simplest exact)
Borůvka (exact) fastest ≤ 12-D (26%+ over KnnGraph at 8-D) dim < 16 ⇒ Borůvka
KnnGraph (~exact) fastest ≥ 16-D (2.8× at 32-D; KD-tree pruning degrades with dim) dim ≥ 16 ⇒ KnnGraph (else Borůvka)

knn_rand = 1.0 across the grid (no measured quality loss vs exact on these blobs). Auto is opt-in (default stays DensePrim). The full per-cell table and the policy rationale are in algorithms.md § MST-backbone auto-selection; caveats: thresholds are multi-core-tuned heuristics with soft boundaries (12-D is a genuine tie).

Backbone refinements since (#73 / #75) — does the matrix need re-running? No. Two further backbone changes have landed (full write-up + measured tables in algorithms.md § MST backbone refinements): a round-adaptive dual-tree that makes exact Borůvka ~1.1–1.5× faster at Dim ≤ 6 (hard-gated above that), and an approximate-k-NN (HNSW) source for KnnGraph that extends the high-d / very-large-n reach. Both are sub-backbone refinements — they change how a given MST is built, not the library's data-dependent defaults — and both are exact-or-equivalent (dual-tree: identical MST weight; HNSW-KnnGraph: Rand = 1.0 vs exact). So the D1–D5 decisions and the reference matrix are unaffected and need no re-run. Two smaller consequences for this section: (1) the sweep table above predates #75, so its low-dim Borůvka cells are now conservative (Borůvka's lead at ≤ 6-D widened — which only reinforces the dim < 16 ⇒ Borůvka policy; no threshold moved); (2) the HNSW-KnnGraph source is a compile-time backend choice, not an Auto option, so it stays out of the selector by design.

D1/D3 follow-up — the OPTICS acquisition crossover (#72)

The OPTICS-side auto-dispatch (NeighborMode::Auto + CoreDistMode::Auto) tunes the two metric-preserving acquisition knobs (Precompute-vs-OnDemand, Scan-vs-Knn) — both byte-identical to the explicit modes, so this is purely a speed study. optics_acq_sweep sweeps ε (hence the average neighborhood size) at fixed n.

Reference run (2026-06-21, 4 threads). The crossover is dimension × density, and it corrects the naïve reading of D3: where the cache fits, Precompute is not always faster —

regime fastest margin
low-D (≤ 8) + dense (avg-nbrs > ~1000) OnDemand + Knn Precompute 3–10× slower (cache memory-traffic, well below the memory wall)
low-D + sparse Precompute + Scan 1.1–2×
high-D (≥ 16), any density Precompute + Scan Knn up to 4× slower (the extra k-NN query is costly in high-D)

So the Auto rule is low-D dense → OnDemand + Knn; else Precompute + Scan, with an OnDemand override when the estimated cache exceeds budget. Full table + rationale in algorithms.md § OPTICS acquisition auto-selection. sOPTICS routing is deliberately not auto (D2 is a metric change, not an engine swap). Auto is opt-in; defaults stay OnDemand + Scan.

Engines compared

engine how status
ours (OPTICS, sOPTICS) optics_quality_compare (C++) built here
scikit-learn (OPTICS xi, HDBSCAN) quality_benchmark.py (Python) runs here
mhahsler/dbscan (R; ANN kd-tree OPTICS) run_dbscan_r.R via quality_benchmark.py runs here (needs R + dbscan)
ELKI (Java; OPTICSXi/FastOPTICS/HDBSCAN*) manual, same CSVs deferred past 1.0.0 (no JVM); matrix Docker env (#59)
NinhPham/sDbscan (C++; sOPTICS competitor) manual, build from source deferred past 1.0.0; matrix Docker env (#59)

R-sandbox note: if a sandboxed R install hides the package from a subprocess, set R_LIBS_USER to the library holding dbscan (Rscript -e "cat(dirname(find.package('dbscan')))"). The harness probes availability and skips the column cleanly otherwise.

Findings (representative, this machine — ratios, not absolutes)

These are the older ad-hoc Franti/toy findings; the authoritative, reproducible numbers are in § 1.0.0 reference benchmark matrix above. They agree, and the Franti-set detail below (R15, D31, aggregation) complements the matrix's synthetic clouds.

  • Speed. At equal eps, ours-OPTICS and dbscan-R are neck-and-neck (e.g. D31 5 vs 7 ms, aggregation 1 vs 2 ms), both ~100–1000× faster than scikit-learn OPTICS (D31 1557 ms; 16-D cosine 7.5 s). Our heap-based seed queue edges out dbscan's linear-scan seed list, most visibly at the larger D31.
  • sOPTICS. Matches the exact methods in its cosine regime (8-D cosine blobs: identical ARI ≈0.78) and is honestly lower on Euclidean layouts (metric mismatch). It crosses over to faster than exact OPTICS only at larger n / higher density (see optics_soptics_compare).
  • Quality parity. At the knee eps, ours-OPTICS matches or beats dbscan-R on most Franti sets (e.g. R15 0.95 vs 0.91, aggregation 0.97 vs 0.54); HDBSCAN is still strongest on a few.
  • Generating-distance estimator matters a lot on clustered data (#57). The uniform-density epsilon_estimation over-shoots on clustered data and over-smooths the reachability, so Xi under-segments — most starkly on R15 (ARI 0.43). The k-distance-knee estimator (epsilon_estimation_knee, #41) lands near the within-cluster scale and recovers it (R15 ARI 0.95), and also helps compound, spiral, and density. The quality harness now defaults to --eps knee (passed to dbscan-R too, so timing stays a fair same-eps comparison). It was NOT the Xi steep-area logic — a decoupled min_cluster_size (added for ELKI parity) had no effect on R15.

TODOs

  • Consider the knee estimator as the auto-eps default DONE (#49/#57): auto-epsilon now defaults to epsilon_estimation_knee across compute_reachability_dists / cluster_threshold / extract_xi (falls back to uniform for non-KnnCoreDist backends and degenerate inputs). Pass an explicit epsilon for the uniform behavior.
  • ~~sOPTICS 16-D quality dip — cos-blobs-16d ARI 0.57 vs ~0.82~~ ADDRESSED (#58): the data-scaled sOPTICS auto-epsilon closes the dip; re-confirm quantitatively in the matrix Tier C/D.
  • Reproduce the dbscan JSS benchmark (replication script) to validate our setup against published numbers, not just same-machine ratios.
  • ELKI + sDbscan columns — DEFERRED past 1.0.0 (decided 2026-06-08). 1.0.0 ships with the scikit-learn + mhahsler/dbscan (R) comparisons only. ELKI needs a JVM and NinhPham/sDbscan needs building from source — both are environment-fragile, so they are pushed to the benchmark matrix's Docker repro env (#59 / ROADMAP-1.0.0-execution.md §B1.5) rather than the local dev sandbox. ELKI remains the FastOPTICS/sOPTICS parity reference when it lands (#53, deferred).
  • FHT structured projections for sOPTICS DONE (#58): opt-in SopticsProjection::Structured (x → H D₃ H D₂ H D₁ x, detail/hadamard.hpp); ~1.2–1.4× at ≥ 64-D.