dKS-3D
Statistics · Algorithms
The exact three-dimensional dKS baseline — a measured, brute-force-checked O(N³) sweep — and the thinning stage being built to outgrow it.
Two samples, P and Q, live in the same three-dimensional space. Take a turn around them.
One point at a time drops its x, y, z onto the three axes — then all of them together. The units disappear; the shared order stays.
A dKS range has one fixed lower corner — everything smaller — and only its far corner z moves.
A point is inside only if it passes all three thresholds; the box's score is the absolute gap between the two inside fractions.
Check every corner of the shared lattice — x, then y, then z fastest. The largest gap over all corners is the exact dKS.
Exact is reliable but worst-case cubic — 0.59 s at n = 400, 10 s at 1,024, and one measured call at n = 8,304 took about 36 minutes.
On one ranked axis: halve, and halve again — dyadic intervals of lengths 1, ½, ¼, at aligned positions.
Pick one dyadic interval on each axis; their product is a rectangular dyadic box — its sides can use different scales.
Any ordinary dominating box is exactly a few dyadic pieces put together — so controlling every piece controls every box.
For P alone, a walk assigns each point + or −, leaning against the imbalance already in its boxes — the imbalance stays bounded, not zero.
A small deterministic repair makes the kept size exactly half; keep the +. Then Q, from scratch — its own walk, no shared labels.
The same recipe runs on the survivors — each round halves what is left.
The exact sweep runs on what remains — exact for the survivors, approximate only through thinning. The near-linear final search is still in progress.
dKS-3D
The exact three-dimensional dKS baseline — a measured, brute-force-checked O(N³) sweep — and the thinning stage being built to outgrow it.
Two point clouds in three dimensions, the exact box sweep that measures their distance, and the thinning stage being built to make it fast.
The 2-D story dKS paper Library (C++/Python)
dKS-3D takes the dKS distance to three dimensions, where the theory says near-linear time is still possible — and where nothing practical existed to run. It is work in progress with Jeff M. Phillips (Kahlert School of Computing, University of Utah); a paper draft is in preparation.
The exact baseline. The first deliverable is an exact algorithm: sweep the thresholds axis by axis and score every dominating box, with no approximation anywhere. It is correctness-tested against an independently written brute-force reference on every build, and its cost is measured, not assumed: time per call follows the predicted cubic curve (log–log slope 2.99, R² > 0.999) from a fraction of a second at n = 400 to about 36 minutes for a single call by n ≈ 8,300. That number is the point: exact is honest but cubic, and the honest baseline is what a fast method must beat.
The thinning stage. The route to fast is the ε-sample reduction: color the points ±1 with a self-balancing walk so that every dyadic box stays nearly balanced, keep one color, and repeat — each round halves the data while the distance over every box moves only a little. The film’s last beats show the mechanism: the coloring, the balanced boxes, the halving. This stage is implemented and under evaluation; the final stage that assembles the full fast pipeline is next.
Discipline. Every number above comes from committed, reproducible experiments — fixed seeds, sanitizer-clean code, and a brute-force oracle that shares no logic with the optimized sweep.