4.8
4.8 | 5 ratings Rate this file 3 Downloads (last 30 days) File Size: 72.9 KB File ID: #3966
image thumbnail

mex_sepsq

by

Ben Mitch (view profile)

 

16 Sep 2003 (Updated )

Fast, dedicated, code to compute Euclidean separation between sets of points in N-dimensional space.

| Watch this File

File Information
Description

To compute the Euclidean separation (L2 norm) between two sets of points in MATLAB can be slow and/or memory-hungry. In some cases (most particularly, if you are working with 2D, 3D or 4D data), this function will do it 2-4 times faster than the fastest m-code I've seen (due to Germano Gomes) and hundreds of times faster than a typical memory-efficient nested loop.

NB: for D much greater than 10-15, performance is better using GG's m-script. See the screenshot for a performance plot - green is GG, blue is mex_sepsq.

>> mex_sepsq_demo
 
A = randn(4, 5000);
B = randn(4, 5000);
 
C1 = mex_sepsq(A, B);
Elapsed time is 0.201335 seconds.
 
C2 = sepsq_gg(A, B);
Elapsed time is 0.517755 seconds.
 
Relative time per implementation: 1.00 2.57

MATLAB release MATLAB 7.10 (R2010a)
Other requirements Must be compiled from source - run "mex_sepsq compile" to do this, usually.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (12)
01 Mar 2011 Ben Mitch

Ben Mitch (view profile)

hi Adam

oh, i've not tried to compile on Win 64-bit, that will probably go awry. to fix (i think), search/replace _MSC_VER with NOTDEF in mex_sepsq.cpp, and try the compile again. you'll get the C version instead of the assembler version (but it's not that much slower). i'll fix this if i ever come across a Win64 install.

cheers

Comment only
01 Mar 2011 Adam Hartshorne

When I try and compile this on a Win 7, 64-bit machine using c++ Visual Studio 2008, get the a long list of the following type of errors,

mex_sepsq compile
mex_sepsq.cpp
c:\users\adam\documents\matlab\mex_sepsq\mex_sepsq_asm.cpp(57) : error C4235: nonstandard extension used : '__asm' keyword not supported on this architecture
c:\users\adam\documents\matlab\mex_sepsq\mex_sepsq_asm.cpp(61) : error C2065: 'push' : undeclared identifier
c:\users\adam\documents\matlab\mex_sepsq\mex_sepsq_asm.cpp(61) : error C2146: syntax error : missing ';' before identifier 'eax'
c:\users\adam\documents\matlab\mex_sepsq\mex_sepsq_asm.cpp(61) : error C2065: 'eax' : undeclared identifier

Comment only
01 Mar 2011 Adam Hartshorne

Forgot to add c++ compiler is Visual Studio 2008.

Comment only
20 Nov 2010 Ben Mitch

Ben Mitch (view profile)

Hi Germano

Wow, what a great function "bsxfun" - . I'd never seen that before (it wasn't available in 2003 when this was written). With that now available, computing this (and other similar tasks) in m-script becomes a lot more efficient, you're right.

I had a play around, and mex_sepsq (the latest version) is a fair bit faster than m-script for D up to around 10 or 15, at which point Matlab's optimised and parallelised matrix libraries get the better of it. In any case, against "bsxfun", the speed-up factor is in 2-4 rather than 15-20, so it's less important. It still has better memory usage, though, using about a third less memory than the m-script implementation.

I've improved the code quite a lot in the process, so I'll upload the latest version - the new code is 2-3 times as fast as the 2003 version for large N, and outperforms the m-script implementation by a factor of 2-3 as well (i.e. the 2003 code performed similarly to your m-script implementation for large N).

I'll also try and include the plots of performance in my upload. It shows the domains where mex_sepsq is worth using. This domain, where mex_sepsq gives a considerable benefit, centres on the obvious 2<D<4 range, so I won't give up on it yet.

Thanks for your interesting comment :)

Comment only
20 Nov 2010 Ben Mitch

Ben Mitch (view profile)

Hi Siyi

Thanks for your comment. There are at least a couple of reasons why I generally store matrices the DxN way, rather than NxD, but neither affects mex_sepsq. I could potentially provide a flag to mex_sepsq to work on data stored the other way round, if you were interested.

Cheers

Comment only
13 Oct 2010 Siyi Deng

Siyi Deng (view profile)

Great function, but its kinda unnatural to use D x N and D x M column vectors. I would argue that the dimensionality should form the columns, so N x D and M x D looks more appropriate.

Comment only
06 Sep 2010 Germano Gomes

I believe that in 3D something like this is almost as fast for number of points >1000, ratio is approximately =2.
function [Dist] = Distance3DFast(M1,M2)
% M1 is a 3xN matrix
% M2 is a 3xM matrix
%Dist is a NxM matrix
%example:
% M1=rand(3, 10000); M2=rand(3,10000);
% Dist=Distance3DFast(M1,M2);
Dist = sqrt(bsxfun(@plus,dot(M1,M1)',dot(M2,M2))-2*M1'*M2);

Comment only
06 Sep 2010 Germano Gomes  
27 Feb 2009 Stanislav  
28 Feb 2008 K Chen

Great

02 Apr 2004 James Alaly

Very fast indeed, thanks for the great function.

17 Sep 2003 roger wan

It is really fast! Thanks.

Updates
30 Aug 2010

Provided a demo and an auto-compile script.

20 Nov 2010

Improved performance, added benchmarking.

22 Nov 2010

whoops, broke the linux implementation - fixed, now.

Contact us