Nearest Neighbor Matching without Replacement

Hello there,

I am looking to match data in two vectors, x and y, based on shortest Euclidean distance. Each match should be unique; that is, numbers in vectors x and y cannot be matched twice. I have looked into knnsearch, but have not found anything that suggests the function works without replacement. Thank you!

[KSSV]

Well, it means for each point you want only one nearest neighbor and this neighbor should not be neighbor to any other point. Is it? If so you have to violate shortest Eucldean distance if neighbor repeats.

[Phillip]

It does not violate the shortest distance if it is removed from the set once matched (what Al is referring too when he says " without Replacement").

[Peng Li]

any update here? also was wondering if there is a way to do knn search without replacement.

Answer 1

[neuroDuck]

A late response, but for anyone that might come across this in future, I think a brute force approach should work, with the following code, assuming you don't have too many comparisons to go through:

[cIdx] = unique(knnsearch(x,y));

% brute force knnsearch to do without replacements
startingK = 2;
while length(cIdx)<length(y)
    [cIdx] = unique(knnsearch(x,y,'k',startingK));
    startingK = startingK + 1;
end

Answer 2

[Bruno Luong]

If you have R2019a release

x=rand(1,10)

x = 1×10

0.7999 0.9374 0.3693 0.3038 0.4504 0.9999 0.9559 0.9041 0.6531 0.1136

y=rand(1,10)

y = 1×10

0.2727 0.5885 0.7090 0.6540 0.6661 0.3712 0.2943 0.0732 0.8695 0.5349

C=abs(x(:)-y(:).');
M = matchpairs(C,max(C(:)));

px = M(:,1);
xm = x(px)

xm = 1×10

0.3693 0.6531 0.9999 0.7999 0.9559 0.4504 0.3038 0.1136 0.9374 0.9041

d = abs(xm-y)

d = 1×10

0.0966 0.0646 0.2910 0.1459 0.2898 0.0792 0.0094 0.0404 0.0679 0.3692