Paper Code Library (C++/Python) Poster (PDF)

dKS extends the classical Kolmogorov–Smirnov distance to multiple dimensions. It is joint work with Peter Matthew Jacobs (University of Wisconsin–Madison) and Jeff M. Phillips (Kahlert School of Computing, University of Utah) — authors are listed alphabetically, following the convention in theory — and is described in our paper, Efficient and Stable Multi-Dimensional Kolmogorov–Smirnov Distance.

The problem. Suppose you weigh a colony of penguins and want to know how different two groups are. Record their body mass in grams or in kilograms and it is the exact same information — yet ask most standard tools to compare the groups and they hand back a different answer just because you switched the units. The comparison ends up measuring your choice of ruler instead of the penguins. And this is not a toy worry: science runs on comparing distributions — lab measurements, clinical cohorts, the data drifting through a production ML system — and a comparison that flinches when the units change cannot be trusted to tell you what actually changed.

How I solved it. In one dimension, statistics solved this back in 1933: the Kolmogorov–Smirnov distance reads only the order of the values, so the ruler drops out of the answer entirely. For ninety years, that guarantee never properly survived the trip to higher dimensions — until dKS carried it across. Switch grams to kilograms and the answer is exactly unchanged, while a popular alternative jumps about 21% (see the experiments below). It is a true metric with provable guarantees — and the algorithm makes it practical: what took the brute-force baseline 4.2 hours at a million samples, dKS answers in a fifth of a second — about 76,000× faster.

Get started

A small, fast open-source library: header-only C++ core with pybind11 Python bindings, correctness-tested against an independent O(n³) brute-force reference, with a CLI included. Both algorithms from the paper ship: exact (dKS-Baseline, O(n²)) and approx (dKS-Sketch, O(n log n)).

#include <dks/dks.hpp>

std::vector<dks::Point> P = {{0.1, 0.2}, {0.5, 0.7}};
std::vector<dks::Point> Q = {{0.2, 0.2}, {0.6, 0.8}};

double d = dks::approx(P, Q);   // dKS-Sketch: fast,  O(n log n)
double e = dks::exact(P, Q);    // dKS-Baseline: exact, O(n^2)

import numpy as np
import dks

P = np.random.rand(1000, 2)
Q = np.random.rand(1000, 2)

dks.approx(P, Q)        # dKS-Sketch: fast O(n log n)
dks.exact(P, Q)         # dKS-Baseline: brute force, exact for P, Q

Why dKS?

Comparing two multi-dimensional distributions shouldn’t depend on the units the data happened to be recorded in — yet for most distances it does. Anything built on a Euclidean ground metric (Maximum Mean Discrepancy, Wasserstein) silently re-weights an axis when you rescale it, and per-axis normalization only defers the problem. The one-dimensional KS distance never had this trouble because it reads only the order of values; dKS carries that property into multiple dimensions — the largest CDF gap over dominating rectangles — making it unit-invariant by construction and, unlike the popular heuristics, a true metric with provable guarantees.

Multi-dimensional two-sample testing is also the primitive behind production data-drift monitoring — comparing training and serving distributions across several features at once. There, unit-invariance removes the fragile per-feature normalization step, the finite-sample guarantees give calibrated alarms instead of heuristic thresholds, and near-linear runtime keeps the check cheap at millions of samples.

What the paper establishes

• A true metric. An integral probability metric with the strong identity property — a genuine metric on distributions, not just a pseudometric.
• Linear sample complexity. Estimating dKS from a sample needs only about (1/ε²)(d + log(1/δ)) points — linear in the dimension d.
• Near-linear computation in 2–4D. ε-approximable in O(n log n) in 2D, with poly-logarithmic factors in 3–4D. Beyond four dimensions, a near-linear algorithm would refute a widely held complexity conjecture — this range is essentially the limit.
• A finite-sample-valid two-sample test. A guaranteed, finite-sample bound on false rejections — not the asymptotic or Monte-Carlo approximations earlier multi-dimensional KS tests relied on.
• Provably stable. The popular quad-KS variant anchors rectangles at the data points, so a single added or removed point can swing it — no sample-complexity bound is possible for it. dKS avoids this by construction.

On real data

Two real datasets, against a Gaussian-kernel MMD — which blends the axes through a Euclidean metric, so its answer depends on the units you happen to choose.

Palmer penguins — body mass vs flipper length

A dKS two-sample test cleanly separates Adelie from Gentoo penguins (p = 0.002). Switch body mass from grams to kilograms, and dKS-Sketch returns the identical value while the Gaussian MMD shifts by up to 21%.

Penguins. Left: the two species are clearly separated (dKS test p = 0.002). Right: switching body mass from grams to kilograms leaves every dKS-Sketch bar (blue) at 1.00, while MMD (red) jumps to 1.21 and 1.16.

NHANES — height vs weight, metric vs US units

5,434 US adults from NHANES 2017–2018. The same person is “178 cm, 82 kg” in metric and “70 in, 181 lb” in US units. dKS-Sketch gives the identical answer for every metric/US choice; MMD changes by up to 39%.

NHANES (5,434 US adults). Left: height vs weight by sex (dKS test p = 0.002). Right: switching cm↔in and kg↔lb leaves dKS-Sketch flat at 1.00 (blue), while MMD (red) drops about 39% from metric to US units — exactly the units artifact dKS is built to avoid.

Citation

@misc{jacobs2025dks,
  title         = {Efficient and Stable Multi-Dimensional Kolmogorov--Smirnov Distance},
  author        = {Jacobs, Peter Matthew and Namjoo, Foad and Phillips, Jeff M.},
  year          = {2025},
  eprint        = {2504.11299},
  archivePrefix = {arXiv},
  primaryClass  = {stat.CO}
}

Authors listed alphabetically.