SMILE — Distance and Metric Functions

The smile.math.distance package provides a rich collection of distance and metric functions used throughout SMILE for nearest-neighbor search, clustering, classification, and other machine-learning algorithms.

Core Abstractions

`Distance<T>`

The root interface for all distance functions. A distance maps every pair of objects to a non-negative real number and satisfies:

Property	Requirement
Non-negativity	`d(x, y) ≥ 0`
Isolation	`d(x, y) = 0` iff `x = y`
Symmetry	`d(x, y) = d(y, x)`

Distance<T> extends ToDoubleBiFunction<T,T> and Serializable, so any instance can be used directly with Java Streams.

java

Distance<double[]> dist = new EuclideanDistance();
double d = dist.d(x, y);
// Also works as a BiFunction:
double d2 = dist.applyAsDouble(x, y);

The interface also provides a pdist(T[] x) default method that computes the full lower-triangular pairwise distance matrix in parallel:

java

double[][] data = { {0, 0}, {3, 0}, {0, 4} };
EuclideanDistance dist = new EuclideanDistance();
Matrix D = dist.pdist(data);
// D.get(1, 0) == 3.0, D.get(2, 0) == 4.0, D.get(2, 1) == 5.0

`Metric<T>`

A Metric is a Distance that additionally satisfies the triangle inequality: d(x, z) ≤ d(x, y) + d(y, z). All standard Lp-norms are metrics.

Dense Vector Distances (`double[]`)

Euclidean Distance

The straight-line distance, also known as the L₂ norm.

d(x, y) = sqrt( Σᵢ (xᵢ - yᵢ)² )

Feature	Detail
Class	`EuclideanDistance`
Implements	`Metric<double[]>`
Weighted	Yes — pass a `double[] weight` to the constructor
NaN handling	NaN values are excluded; result is scaled by `n/m`
Sparse	`SparseEuclideanDistance` for `SparseArray` inputs

java

// Unweighted
EuclideanDistance dist = new EuclideanDistance();
double d = dist.d(new double[]{1, 2, 3}, new double[]{4, 3, 2});
// d ≈ 3.742

// Weighted
double[] w = {2.0, 1.0, 0.5};
EuclideanDistance wDist = new EuclideanDistance(w);

// Sparse
SparseEuclideanDistance sparseDist = new SparseEuclideanDistance();
double sd = sparseDist.d(sparseX, sparseY);

Manhattan Distance

The sum of absolute differences, also known as the L₁ norm or city-block distance.

d(x, y) = Σᵢ |xᵢ - yᵢ|

Feature	Detail
Class	`ManhattanDistance`
Implements	`Metric<double[]>`
Weighted	Yes
NaN handling	NaN values excluded; result scaled by `n/m`
Sparse	`SparseManhattanDistance`

java

ManhattanDistance dist = new ManhattanDistance();
double d = dist.d(new double[]{1, 2, 3}, new double[]{4, 3, 2});
// d = |1-4| + |2-3| + |3-2| = 5

// Integer array shortcut (no NaN handling):
int[] x = {1, 2, 3, 4};
int[] y = {4, 3, 2, 1};
double di = new ManhattanDistance().d(x, y); // 8

Chebyshev Distance

The maximum absolute difference over all dimensions, also known as the L∞ norm or chessboard distance.

d(x, y) = maxᵢ |xᵢ - yᵢ|

Feature	Detail
Class	`ChebyshevDistance`
Implements	`Metric<double[]>`
NaN handling	NaN values excluded
Sparse	`SparseChebyshevDistance`

java

ChebyshevDistance dist = new ChebyshevDistance();
double d = dist.d(new double[]{1, 5, 3}, new double[]{4, 2, 1});
// d = max(|1-4|, |5-2|, |3-1|) = 3

Minkowski Distance

The general Lp norm, parameterized by order p.

d(x, y) = ( Σᵢ |xᵢ - yᵢ|ᵖ )^(1/p)

Special cases: p=1 → Manhattan, p=2 → Euclidean, p→∞ → Chebyshev.

Feature	Detail
Class	`MinkowskiDistance`
Implements	`Metric<double[]>`
Weighted	Yes
NaN handling	NaN values excluded; result scaled appropriately
Sparse	`SparseMinkowskiDistance`

java

MinkowskiDistance m3 = new MinkowskiDistance(3);  // L3 norm
double d = m3.d(x, y);

// Weighted L4
MinkowskiDistance wm4 = new MinkowskiDistance(4, weights);

Mahalanobis Distance

A scale-invariant distance that accounts for correlations among variables using a covariance matrix Σ.

d(x, y) = sqrt( (x-y)ᵀ Σ⁻¹ (x-y) )

When Σ = I (identity), Mahalanobis reduces to Euclidean distance.

java

double[][] cov = {
    {0.9, 0.4, 0.7},
    {0.4, 0.5, 0.3},
    {0.7, 0.3, 0.8}
};
MahalanobisDistance dist = new MahalanobisDistance(cov);
double d = dist.d(x, y);

Statistical / Probabilistic Distances

Correlation Distance

Defined as 1 − r(x, y) where r is the correlation coefficient. Range is [0, 2] — value 0 means perfect positive correlation, 2 means perfect negative correlation.

Supports three correlation methods:

Method	Class constructor argument
Pearson	`"pearson"` (default)
Spearman (rank)	`"spearman"`
Kendall (tau)	`"kendall"`

java

CorrelationDistance pearson   = new CorrelationDistance();           // Pearson
CorrelationDistance spearman  = new CorrelationDistance("spearman");
CorrelationDistance kendall   = new CorrelationDistance("kendall");

double[] x = {1.0, 2.0, 3.0, 4.0};
double[] y = {4.0, 3.0, 2.0, 1.0};
double d = pearson.d(x, y); // 2.0 (perfectly anti-correlated)

Jensen-Shannon Distance

The square root of the Jensen-Shannon divergence between two probability distributions P and Q:

JSD(P‖Q) = ( KL(P‖M) + KL(Q‖M) ) / 2,   M = (P + Q) / 2
d(P, Q)  = sqrt( JSD(P‖Q) )

This is a proper metric bounded in [0, 1] (with natural logarithm).

java

double[] p = {0.3, 0.4, 0.3};
double[] q = {0.5, 0.2, 0.3};
JensenShannonDistance dist = new JensenShannonDistance();
double d = dist.d(p, q);

Set / Categorical Distances

Jaccard Distance

Measures dissimilarity between two sets as the complement of the Jaccard similarity coefficient:

d(A, B) = 1 − |A ∩ B| / |A ∪ B|

Works on both Set<T> and T[] inputs:

java

// On arrays (generic type)
JaccardDistance<String> dist = new JaccardDistance<>();
String[] a = {"cat", "dog", "bird"};
String[] b = {"dog", "bird", "fish"};
double d = dist.d(a, b); // 1 - 2/4 = 0.5

// Static helper for java.util.Set
Set<Integer> s1 = Set.of(1, 2, 3, 4);
Set<Integer> s2 = Set.of(3, 4, 5, 6);
double d2 = JaccardDistance.d(s1, s2); // 1 - 2/6 ≈ 0.667

Hamming Distance

Counts the number of positions where two strings or arrays differ. For integers and longs, uses the hardware POPCNT instruction via Integer.bitCount / Long.bitCount.

java

// Integer arrays
HammingDistance dist = new HammingDistance();
int[] x = {1, 0, 1, 1, 0};
int[] y = {1, 0, 0, 1, 1};
double d = dist.d(x, y); // 2

// Bit-level (single integer)
int d2 = HammingDistance.d(0x5D, 0x49); // 2

// Long integer
int d3 = HammingDistance.d(0xFFL, 0x00L); // 8

// Byte arrays
byte[] bx = {1, 0, 1, 1, 1, 0, 1};
byte[] by = {1, 0, 0, 1, 0, 0, 1};
int d4 = HammingDistance.d(bx, by); // 2

// BitSet
HammingDistance hd = new HammingDistance();
double d5 = hd.d(bitSetX, bitSetY);

Lee Distance

A generalization of Hamming distance for q-ary alphabets {0, 1, …, q−1}. Each symbol comparison wraps around modulo q:

d(x, y) = Σᵢ min( |xᵢ − yᵢ|,  q − |xᵢ − yᵢ| )

When q = 2 or q = 3, Lee distance equals Hamming distance.

java

// Alphabet size q=6
LeeDistance dist = new LeeDistance(6);
int[] x = {3, 3, 4, 0};
int[] y = {2, 5, 4, 3};
double d = dist.d(x, y); // 6

// Wrap-around: |0 - 5| = 5, but min(5, 6-5) = 1
int[] x2 = {0};
int[] y2 = {5};
double d2 = new LeeDistance(6).d(x2, y2); // 1

Sequence Distances

Edit Distance (Levenshtein / Damerau)

Edit distance counts the minimum number of single-character edit operations needed to transform one string into another.

Variant	Allowed operations
Levenshtein	insert, delete, substitute
Damerau-Levenshtein	insert, delete, substitute, transpose adjacent

Two implementations are provided:

Static methods — simple O(mn) dynamic programming, multi-thread safe:

java

// Levenshtein
int d1 = EditDistance.levenshtein("kitten", "sitting"); // 3

// Damerau (cheaper for transpositions)
int d2 = EditDistance.damerau("act", "cat"); // 1 (one transposition)

Instance (BR algorithm) — faster O(kn) algorithm when the distance is small, pre-allocates working arrays:

java

// Unit cost, Levenshtein
EditDistance lev = new EditDistance(maxLen, false);
double d1 = lev.d("Levenshtein", "Laeveshxtin"); // 4

// Unit cost, Damerau
EditDistance dam = new EditDistance(maxLen, true);
double d2 = dam.d("act", "cat"); // 1

Weighted edit distance — custom substitution, insertion and deletion costs via a CharSubstitutionCost table:

java

EditDistance wEdit = new EditDistance(substitutionCostTable, maxLen);

Dynamic Time Warping (DTW)

DTW aligns two time series non-linearly to measure their similarity independent of temporal distortions. An optional Sakoe-Chiba band constrains the warp window to improve both accuracy and speed.

java

double[] x = { /* time series 1 */ };
double[] y = { /* time series 2 */ };

// Unconstrained DTW
double d1 = DynamicTimeWarping.d(x, y);

// With Sakoe-Chiba band: radius = 20 steps
double d2 = DynamicTimeWarping.d(x, y, 20);

// float[] and int[] overloads are also available
float[] xf = { /* ... */ };
double d3 = DynamicTimeWarping.d(xf, yf);

For generic types, use the DynamicTimeWarping<T> class with any Distance<T>:

java

// DTW on boxed Double sequences
Distance<Double> absDiff = (a, b) -> Math.abs(a - b);
DynamicTimeWarping<Double> dtw = new DynamicTimeWarping<>(absDiff);

Double[] xa = {1.0, 2.0, 3.0};
Double[] ya = {1.0, 2.0, 4.0};
double d = dtw.d(xa, ya); // 1.0

// With radius (percentage of sequence length)
DynamicTimeWarping<Double> dtwBand = new DynamicTimeWarping<>(absDiff, 0.1);

Sparse Array Distances

All standard Lp distances have counterparts that work on SparseArray (indices stored as sorted int arrays):

Dense class	Sparse class
`EuclideanDistance`	`SparseEuclideanDistance`
`ManhattanDistance`	`SparseManhattanDistance`
`ChebyshevDistance`	`SparseChebyshevDistance`
`MinkowskiDistance`	`SparseMinkowskiDistance`

java

SparseArray s1 = new SparseArray();
s1.append(0, 3.0);
s1.append(2, 4.0);

SparseArray s2 = new SparseArray();
s2.append(1, 5.0);
s2.append(2, 1.0);

double d = new SparseEuclideanDistance().d(s1, s2);

NaN Handling

EuclideanDistance, ManhattanDistance, and MinkowskiDistance (and their sparse variants) treat NaN values as missing. The distance is computed on the m non-missing pairs, then scaled up by n/m to restore the same expected magnitude as if all n dimensions were observed.

If all values are NaN, Double.NaN is returned.

java

double[] x = {Double.NaN, 3.0, 4.0};
double[] y = {1.0, Double.NaN, 1.0};
// Only index 2 contributes: |4-1| = 3; n=3, m=1
// Result = sqrt(3 * 9 / 1) = sqrt(27) ≈ 5.196
double d = new EuclideanDistance().d(x, y);

Choosing the Right Distance

Use case	Recommended distance
General continuous data	`EuclideanDistance`
Outlier-robust / sparse differences	`ManhattanDistance`
Data with correlated features	`MahalanobisDistance`
Variable-length sequences	`DynamicTimeWarping`
String / character sequences	`EditDistance`
Sets / binary features	`JaccardDistance`, `HammingDistance`
Probability distributions	`JensenShannonDistance`
Cyclic integer symbols	`LeeDistance`
Smooth distributions (kernel trick)	prefer a kernel; see `smile.math.kernel`

SMILE — Distance and Metric Functions

SMILE — Distance and Metric Functions

Core Abstractions

Distance<T>

Metric<T>

Dense Vector Distances (double[])

Euclidean Distance

Manhattan Distance

Chebyshev Distance

Minkowski Distance

Mahalanobis Distance

Statistical / Probabilistic Distances

Correlation Distance

Jensen-Shannon Distance

Set / Categorical Distances

Jaccard Distance

Hamming Distance

Lee Distance

Sequence Distances

Edit Distance (Levenshtein / Damerau)

Dynamic Time Warping (DTW)

Sparse Array Distances

NaN Handling

Choosing the Right Distance

`Distance<T>`

`Metric<T>`

Dense Vector Distances (`double[]`)