Distance functions

L1()

The manhattan distance or $L_1$ is defined as

\[L_1(u, v) = \sum_i{|u_i - v_i|}\]

L2()

The euclidean distance or $L_2$ is defined as

\[L_2(u, v) = \sqrt{\sum_i{(u_i - v_i)^2}}\]

SqL2()

The squared euclidean distance is defined as

\[L_2(u, v) = \sum_i{(u_i - v_i)^2}\]

It avoids the computation of the square root and should be used whenever you are able do it.

LInfty()

The Chebyshev or $L_{\infty}$ distance is defined as

\[L_{\infty}(u, v) = \max_i{\left| u_i - v_i \right|}\]

Lp(p)
Lp(p, pinv)

The general Minkowski distance $L_p$ distance is defined as

\[L_p(u, v) = \left|\sum_i{(u_i - v_i)^p}\right|^{1/p}\]

Where $p_{inv} = 1/p$. Note that you can specify unrelated p and pinv if you need an specific behaviour.

Cosine()

The cosine is defined as:

\[\cos(u, v) = \frac{\sum_i u_i v_i}{\sqrt{\sum_i u_i^2} \sqrt{\sum_i v_i^2}}\]

The cosine distance is defined as $1 - \cos(u,v)$

NormCosine()

Similar to Cosine but suppose that input vectors are already normalized, and therefore, reduced to simply one minus the dot product.

\[1 - \sum_i {u_i v_i}\]

Angle()

The angle distance is defined as:

\[∠(u, v)= \arccos(\cos(u, v))\]

NormAngle()

Similar to Angle but suppose that input vectors are already normalized

\[\arccos \sum_i {u_i v_i}\]

Jaccard()

The Jaccard distance is defined as

\[J(u, v) = \frac{|u \cap v|}{|u \cup v|}\]

Dice()

The Dice distance is defined as

\[D(u, v) = \frac{2 |u \cap v|}{|u| + |v|}\]

Intersection()

The intersection dissimilarity uses the size of the intersection as a mesuare of similarity as follows:

\[I(u, v) = 1 - \frac{|u \cap v|}{\max \{|u|, |v|\}}\]

CosineSet()

The cosine distance for very sparse binary vectors represented as sorted lists of positive integers where ones occur.

RogersTanimoto(σ)

The Rogers-Tanimoto dissimilarity for very sparse binary vectors represented as sorted lists of positive integers where ones occur (as with Jaccard, Dice, and CosineSet). The field σ is the size of the full universe, i.e., the total number of possible elements/dimensions, and is used to recover the number of positions where both a and b are zero.

Using the usual contingency-table notation for two binary vectors, with $tt$ the number of shared ones (the intersection size), $tf$ and $ft$ the number of ones that appear in only one of the two sets, and $ff = \sigma - tt - tf - ft$ the number of shared zeros, the Rogers-Tanimoto dissimilarity is defined as

\[RT(u, v) = 1 - \frac{tt + ff}{tt + ff + 2(tf + ft)}\]

Access via Dist.Sets.RogersTanimoto.

Examples

d = Dist.Sets.RogersTanimoto(σ)
evaluate(d, u, v)

Hamming()

Binary hamming uses bit wise operations to count the differences between bit strings

RogersTanimoto()

The Rogers-Tanimoto dissimilarity for binary vectors represented as arrays of unsigned integers (bit strings), where each bit is a binary attribute. Access via Dist.Bits.RogersTanimoto.

Using $tt$ for the number of bits set to one in both a and b, $ff$ for the number of bits set to zero in both, and $tf$, $ft$ for the number of mismatching bits, the dissimilarity is defined as

\[RT(u, v) = 1 - \frac{tt + ff}{tt + ff + 2(tf + ft)}\]

Examples

d = Dist.Bits.RogersTanimoto()
evaluate(d, u, v)

RussellRao()

The Russell-Rao dissimilarity for binary vectors represented as arrays of unsigned integers (bit strings), where each bit is a binary attribute. Access via Dist.Bits.RussellRao.

It measures the fraction of bits set to one in both a and b ($tt$) with respect to the total number of bits $n$ (computed as length(a) * 64, i.e., it assumes 64-bit words):

\[RR(u, v) = 1 - \frac{tt}{n}\]

Examples

d = Dist.Bits.RussellRao()
evaluate(d, u, v)

CommonPrefix()

Uses the common prefix as a measure of dissimilarity between two strings

Levenshtein(; icost=1, dcost=1, rcost=1)
Levenshtein(ctx; icost=1, dcost=1, rcost=1)

The levenshtein distance measures the minimum number of edit operations to convert one string into another. The costs insertion icost, deletion cost dcost, and replace cost rcost.

Scratch buffers, and why there is no lock

evaluate needs a row of Int16s (plus, for AbstractString inputs, a Vector{Char}). A Levenshtein built the ordinary way owns no scratch and allocates what it needs per call, which is what makes it safe to share across tasks unconditionally – there is no mutable state to race on, under any scheduler or any concurrency model of your own.

To skip even that allocation, ask beginbatch for a batch-local copy at the top of a @BATCHES batch (bdist = beginbatch(distance(index))) and use that inside the batch. The copy owns private buffers it grows once and reuses; a batch is single-tasked, so nothing guards them and nothing needs to.

This replaced a Channel-based buffer pool. The pool was safe, but its take!/put! pair per call turned out to cost far more than the work it was protecting whenever evaluations are cheap: on a 200k-element parallel map of 5-10 character words over 64 threads it was ~80x slower than allocating (302ms vs 3.6ms), and it lost even single-threaded.

ctx is still accepted and ignored, so old call sites keep working – it used to size the pool. It will go away in 2.0.

AbstractString inputs (String, SubString, ...)

a/b can be passed as plain String/SubString directly – Unicode included – with no need to collect them into a Vector{Char} first. A dedicated method (see below) walks each string with Julia's string-iteration protocol (for c in s, the efficient, allocation-free equivalent of repeatedly calling nextind) instead of integer-indexing s[i] for i in 1:length(s), which is what the generic evaluate(::Levenshtein, a, b) method above does and why it throws StringIndexError on a String/SubString containing non-ASCII characters (a String is indexed by codeunit – a byte, for its UTF-8 encoding – not by character, and only ASCII characters take exactly one codeunit each). The shorter of the two strings is decoded once into a second pooled scratch buffer (see the scratch section above) so it can be randomly indexed inside the O(alen*blen) dynamic-programming loop; the longer one is walked forward-only and never needs random access, so it costs nothing beyond that same forward pass.

DamerauLevenshtein(; icost=1, dcost=1, rcost=1, tcost=1)
DamerauLevenshtein(ctx; icost=1, dcost=1, rcost=1, tcost=1)

The restricted Damerau-Levenshtein distance (a.k.a. Optimal String Alignment, OSA): Levenshtein extended with a fourth edit operation, the transposition of two adjacent characters, at cost tcost. This captures a common typo pattern, e.g. "form" -> "from" (the middle "or" swapped to "ro"), as a single edit instead of two substitutions.

This is the restricted variant: it disallows editing a substring that already participated in a transposition again, which is what keeps the algorithm inside the same row-by-row scratch-buffer scheme as Levenshtein (a small extra lookback row, rather than a full O(alen*blen) matrix). The consequence is that this distance is a SemiMetric, not a Metric: it satisfies d(a,a) == 0 and d(a,b) == d(b,a), but not the triangle inequality (e.g. evaluate(dl, "ca", "abc") can exceed evaluate(dl, "ca", "ac") + evaluate(dl, "ac", "abc")) – the unrestricted/"true" Damerau-Levenshtein distance that does satisfy it needs the full matrix and is not implemented here.

AbstractString inputs (String, SubString, ...)

a/b can be passed as plain String/SubString directly – Unicode included – via a dedicated method (see below); see Levenshtein's docstring for why the generic evaluate(::DamerauLevenshtein, a, b) method above throws StringIndexError on those inputs and how the AbstractString method avoids it (string-iteration instead of s[i]-indexing, plus a scratch buffer holding the shorter string's characters).

evaluate(::DamerauLevenshtein, a, b) handles scratch exactly as Levenshtein does – allocated per call unless beginbatch handed out a batch-local copy, never locked – the only difference being that three rolling rows (current, previous, and two-rows-back, for the transposition lookback) share one buffer instead of one row using it.

Hamming()

The hamming distance counts the differences between two equally sized strings

LCS()
LCS(ctx)

Instantiates a Levenshtein object to perform LCS distance. See Levenshtein for the meaning of ctx (optional; sizes the internal scratch pool from ctx.maxbatches).

Hausdorff(dist::PreMetric)

Hausdorff distance is defined as the maximum of the minimum between two clouds of points.

\[Hausdorff(U, V) = \max{\max_{u \in U} nndist(u, V), \max{v \in V} nndist(v, U) }\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

DirectedHausdorff(dist::PreMetric)

The directed (one-sided) Hausdorff distance from a cloud of points u to a cloud v: how far you'd have to look, starting from the point of u that is worst served by v, to find its nearest neighbor in v. Unlike Hausdorff (its symmetrized, two-sided counterpart), this is generally not symmetric: evaluate(d, u, v) != evaluate(d, v, u) in general, since swapping which cloud is "covered by" the other measures a different quantity.

\[DirectedHausdorff(U, V) = \max_{u \in U} nndist(u, V)\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

Examples

d = Dist.Cloud.DirectedHausdorff(Dist.L2())
evaluate(d, U, V)  # how far U strays from V
evaluate(d, V, U)  # how far V strays from U -- not the same value in general

Chamfer(distance)

Computes the Chamfer dissimilarity between two point clouds

\[Chamfer(U, V) = \frac{1}{|U|}\sum_{u \in U} nndist(u, V) + \frac{1}{|V|}\sum_{v \in V} nndist(v, U)\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

EMD(dist, p)

Approximates the Earth Mover's Distance (EMD) between two point clouds U and V of the same size as a greedy perfect matching: points are matched one at a time, each being paired with its nearest still-unmatched point in the other cloud (measured with dist), and the distances of the matched pairs are then combined with an $L_p$-like aggregation.

Arguments

• dist: the base distance function used to compare individual points of the clouds.
• p: the exponent used to combine the distances of the matched pairs, i.e.,

\[EMD(U, V) = \left(\sum_i evaluate(dist, u_i, v_{\pi(i)})^p \right)^{1/p}\]

where $\pi$ is the greedy matching found by the algorithm.

Note that this is a greedy approximation of the assignment problem underlying the exact EMD (optimal transport), not the exact solution, and it requires length(U) == length(V).

Examples

d = Dist.Cloud.EMD(Dist.L2(), 2f0)
evaluate(d, U, V)

NegativeDistanceHack(dist)

Evaluates as the negative of the distance function being wrapped. This is not a real distance function but a simple hack to get a similarity and use it for searching for farthest elements (farthest points / farthest pairs) on indexes that can handle this hack (e.g., ExhaustiveSearch, ParallelExhaustiveSearch, SearchGraph).

SimilarityFromDistance(dist)

Evaluates as $1/(1 + d)$ for a distance evaluation $d$ of dist. This is not a distance function and is part of the hacks to get a similarity for searching farthest elements on indexes that can handle this hack (e.g., ExhaustiveSearch, ParallelExhaustiveSearch, SearchGraph).

DistanceWithIdentifiers(distance, database)

Wraps the given database and distance with a proxy database that is accessed with integers from 1 to n

L1()

Float32-casting variant of Dist.L1, the Manhattan or $L_1$ distance

\[L_1(u, v) = \sum_i{|u_i - v_i|}\]

Every element of u and v is cast to Float32 before accumulating the sum, regardless of the input element type. Access via Dist.CastF32.L1.

Examples

d = Dist.CastF32.L1()
evaluate(d, u, v)

L2()

Float32-casting variant of Dist.L2, the euclidean or $L_2$ distance

\[L_2(u, v) = \sqrt{\sum_i{(u_i - v_i)^2}}\]

Every element of u and v is cast to Float32 before accumulating the sum, regardless of the input element type. Access via Dist.CastF32.L2.

Examples

d = Dist.CastF32.L2()
evaluate(d, u, v)

SqL2()

Float32-casting variant of Dist.SqL2, the squared euclidean distance

\[L_2(u, v) = \sum_i{(u_i - v_i)^2}\]

It avoids the computation of the square root, and every element of u and v is cast to Float32 before accumulating the sum, regardless of the input element type. Access via Dist.CastF32.SqL2.

Examples

d = Dist.CastF32.SqL2()
evaluate(d, u, v)

Lp(p)
Lp(p, pinv)

Float32-casting variant of Dist.Lp, the general Minkowski $L_p$ distance

\[L_p(u, v) = \left|\sum_i{(u_i - v_i)^p}\right|^{1/p}\]

where $p_{inv} = 1/p$ (you may specify unrelated p and pinv if needed). Every element of u and v is cast to Float32 before accumulating the sum, regardless of the input element type. Access via Dist.CastF32.Lp.

Examples

d = Dist.CastF32.Lp(3f0)
evaluate(d, u, v)

LInfty()

Float32-casting variant of Dist.LInfty, the Chebyshev or $L_{\infty}$ distance

\[L_{\infty}(u, v) = \max_i{\left| u_i - v_i \right|}\]

Every element of u and v is cast to Float32 before computing the maximum, regardless of the input element type. Access via Dist.CastF32.LInfty.

Examples

d = Dist.CastF32.LInfty()
evaluate(d, u, v)

Cosine()

Float32-casting variant of Dist.Cosine. The cosine distance is defined as

\[1 - \cos(u, v) = 1 - \frac{\sum_i u_i v_i}{\sqrt{\sum_i u_i^2}\sqrt{\sum_i v_i^2}}\]

Every element of u and v is cast to Float32 before accumulating the dot product and norms, regardless of the input element type. Access via Dist.CastF32.Cosine.

Examples

d = Dist.CastF32.Cosine()
evaluate(d, u, v)

NormCosine()

Float32-casting variant of Dist.NormCosine. Assumes that u and v are already normalized, which reduces the cosine distance to $1 - \sum_i u_i v_i$, with every element cast to Float32 before accumulating the dot product. Access via Dist.CastF32.NormCosine.

Examples

d = Dist.CastF32.NormCosine()
evaluate(d, u, v)

Angle()

Float32-casting variant of Dist.Angle. Computes the angle between u and v as $\arccos(\cos(u, v))$, casting every element of u and v to Float32 before accumulating the dot product and norms. Access via Dist.CastF32.Angle.

Examples

d = Dist.CastF32.Angle()
evaluate(d, u, v)

NormAngle()

Float32-casting variant of Dist.NormAngle. Assumes that u and v are already normalized, computing $\arccos\left(\sum_i u_i v_i\right)$, with every element cast to Float32 before accumulating the dot product. Access via Dist.CastF32.NormAngle.

Examples

d = Dist.CastF32.NormAngle()
evaluate(d, u, v)