search

flann-lib / flann

Fast Library for Approximate Nearest Neighbors
http://people.cs.ubc.ca/~mariusm/flann
Other
2.21k stars 646 forks source link

'Composite' mode has duplicate results (nearest neighbors not unique) #505

Open Reederoo opened 1 year ago

Reederoo commented 1 year ago

I wrote a Matlab function to check the uniqueness of the results index matrix and found that when the algorithm is 'composite', the results are up to 25% duplicate indices. None of the other algorithms produce any duplicate indices so I think this is a bug in 'composite'.

function avg_uniqueness = calculateUniqueness(result) k = size(result,1); % The number of neighbors n = size(result,2); % The number of query points total_uniqueness = 0; for i=1:n % Count the number of unique neighbors for this query point unique_count = length(unique(result(:, i))); % Calculate the uniqueness fraction for this query point uniqueness = unique_count / k; % Add it to the total uniqueness total_uniqueness = total_uniqueness + uniqueness; end % Calculate the average uniqueness avg_uniqueness = total_uniqueness / n; end

stephematician commented 11 months ago

Even though I don't have MATLAB I can confirm this.

This occurs when a CompositeIndex is searched without ensuring that a heap-based ResultSet is used; I'll add this to my fork (as it appears FLANN is not being updated anymore).