# speed up ismember with two-dim data

3 views (last 30 days)
Felix Müller on 13 Jul 2021
Commented: Felix Müller on 15 Jul 2021
I have two large cell-arrays (X and Y) where each field is a two dimensional array representing pixel positions. The cell arrays are not the same size (can be in the range of thousands) and each entry can be be a different length (ranging from length 1 to length >1000). Maybe relevant: Over X and Y individually, no point can be included twice, i.e. all entries in X have no points in common (same for Y).
Now I want to find the overlap between all entries in X with all entries in Y. (in reality I filter the entries in Y for a criterion and compute only roughly 10-20 percent of the comparisons)
Is there a way to speed up this process? I have read about ismembc which requires sorted data (and thus I thought it cannot be used in my case).
Minimal working example:
X{1} = [1 1; 1 2; 1 3];
X{2} = [3 1; 3 2; 3 3];
Y{1} = [1 1; 1 2];
Y{2} = [2 3; 3 1; 3 2; 3 3];
Y{3} = [5 5];
mat_overlap = NaN(length(X), length(Y));
for ii = 1:length(X)
for jj = 1:length(Y)
mat_overlap(ii,jj) = sum(ismember(X{ii}, Y{jj}, 'rows'));
end
end
Felix Müller on 15 Jul 2021
True, typo! (I tested with my real data)
Yes, that can well be! I'll make it clearer in my answer above. I tested my whole routine which does other things as well besides only using ismember/ismembc and the 60% speed up was for that. For the raw comparison it will be much more but of course that is the interesting number here!

Jan on 14 Jul 2021
function Test_Felix
X = TestData;
Y = TestData;
% Original method:
tic;
mat_overlap = NaN(length(X), length(Y));
for ii = 1:length(X)
for jj = 1:length(Y)
mat_overlap(ii,jj) = sum(ismember(X{ii}, Y{jj}, 'rows'));
end
end
toc
% Modified:
tic;
nX = numel(X); % Condense the 2 columns to 1:
X2 = cell(1, nX);
for iX = 1:nX
X2{iX} = X{iX}(:,1) * 5000 + X{iX}(:, 2);
end
nY = numel(Y);
Y2 = cell(1, nY);
for iY = 1:nY
Y2{iY} = Y{iY}(:,1) * 5000 + Y{iY}(:, 2);
end
mat_overlap2 = NaN(nX, nY);
for iY = 1:nY % Swap loops
Yi = sort(Y2{iY}); % Sort once only
for iX = 1:nX
mat_overlap2(iX, iY) = sum(ismembc(X2{iX}, Yi));
end
end
toc
isequal(mat_overlap, mat_overlap2)
end
function X = TestData
n = 200;
X = cell(1, n);
arr = randi([15, 1500], n, 1);
num_total = sum(arr);
% create vector with unique rows
random_vector = [];
while length(random_vector) < num_total
num_missing = num_total - length(random_vector);
append = round(4000*rand(num_missing, 2));
random_vector = unique([random_vector; append], 'rows');
end
% fill X with the correct different lengths
for k = 1:n
idx_first = sum(arr(1:(k-1))) + 1;
idx_last = sum(arr(1:k));
X{k} = random_vector(idx_first:idx_last, :);
end
end
Timings on Matlab R2018b, i5 mobile:
Elapsed time is 17.209408 seconds.
Elapsed time is 0.175748 seconds.
A factor of 100. Nice! I've reduced the data size from n=1000 to 200 for faster tests.
##### 1 CommentShowHide None
Felix Müller on 15 Jul 2021
wonderful!

R2020b

### Community Treasure Hunt

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

Start Hunting!