The most efficient pairwise distance computation

Version 1.2.1 (4.67 KB) by wfH
Enhannced `pdist2`! Vectorized code that achieve 10x~100x efficienficy for nD-array (i.g., i-by-j-by-k). Support many distance metrics.


Updated 14 Dec 2022

View License

In human motion analysis, a commond need is the computation of the distance between defferent point sets.
The builtin function `pdist2` could be helpful, but it is inefficient for multiple timeframes data.
Currently avaliable codes in FEX are also insufficient as they can only compute (squared) Euclidean distance and they still cannot handle nD-array.
Therefore, I created this handy function `markerdistance` to enhance `pdist2`.
My code is vectorized to achieve 10x~100x efficienficy for nD-array (i.g., i-by-j-by-k).
Additionally, `markerdistance` supports many different distance metrics, including 'euclidean', 'cityblock', 'chebychev', 'minkowski', 'cosine', 'correlation', 'mahalanobis', 'chisquare', and 'Earth's mover' distance.
This function heavly depends on the calculation of vector-wise norm.
If you don't have the builtin `vecnorm` that was introduced in R2017b, use local subfunction `ndnorm` as an alternative (all you need to do is simply replace `vecnorm` with `ndnorm`).
Computation of Mahalanobis distance requires `pagetranspose`, `pagemtimes`, and 'pageinv'.
I don't really know much about the measurements above as I am not working at these research fields.
All I did is vectorize the codes for nD-array. Don't blame on me if the results are not what you expected.
The following code is for demo.
metric = 'euclidean'; % euclidean, cityblock, chebychev, cosine, correlation, mahalanobis
Xn = randi([1, 10], 1);
Yn = randi([1, 10], 1);
d = 3;
slice = 123456;
X = rand(Xn, d, slice);
Y = rand(Yn, d, slice);
D1 = markerdistance(X, Y, metric);
t1 = toc
D2 = zeros(Xn, Yn, slice);
for pp2 = 1:slice
D2(:, :, pp2) = pdist2(X(:, :, pp2), Y(:, :, pp2), metric);
t2 = toc
efficiency = t2/t1
reserr = max(abs(D1(:)-D2(:)), [], 1)
if strncmpi(metric, 'e', 1)
% `sqdist` could be found in FEX
D3 = zeros(Xn, Yn, slice);
for pp3 = 1:slice
D3(:, :, pp3) = sqdist(X(:, :, pp3).', Y(:, :, pp3).');
D3 = sqrt(D3);
t3 = toc
efficiency2 = t3/t1
reserr2 = max(abs(D1(:)-D3(:)), [], 1)
% Note. For large-scale data (e.g., Xn or Yn is large), `sqdist` might be better.
No more for-loop!

Cite As

wfH (2023). The most efficient pairwise distance computation (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2022b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

feat(measure): support Mahalanobis distance, Chi-squared distance, and Earth Mover's distance.
doc(help): typo & table of measures.


fix `ndnorm`