MATLAB exact knn problem

Hi,

I'm trying to use FLANN's kd-tree implementation for some work with exact nearest neighbor search. As far as I understand, using 1 kdtree and setting checks to -1 (FLANN_CHECKS_UNLIMITED) should provide exact nearest neighbors. However, this doesn't seem to be the case.

I run the following matlab script with a freshly built version of flann 1.7.1:

addpath('flann-1.7.1-src/src/matlab');

data = single(rand(2,1e3));
test = single(rand(2,1));

idx = flann_build_index(data,struct('algorithm','kdtree','trees',1));
res = flann_search (idx, test, 50, struct('checks',-1));    
% -1 is FLANN_CHECKS_UNLIMITED
flann_free_index(idx);

rmax = sqrt(max(sum( bsxfun(@minus, data(:,res), test).^2)))
% rmax is the distance of the worst neighbor found
linres = find( (sum( bsxfun(@minus, data, test).^2)) <= rmax^2 );
% linres are results from linear scan up to rmax
length(linres)

% plot data and neighbors to see problem
plot(data(1,:),data(2,:),'kx')
hold all;
axis equal;
plot(test(1),test(2),'bx',data(1,res),data(2,res),'ro');
rectangle('position',[test'-[rmax,rmax] [2*rmax 2*rmax]],'curvature',[1 1]);
hold off;

The results:

rmax =

    0.1238

ans =

    53

This means that even though I searched for the 50 nearest neighbors, there are actually 3 more neighbors closer than the worst neighbor that FLANN finds. The plot shows this problem clearly - some points close to the query are not reported as neighbors, while further points are. If I run the script repeatedly, the number of errors fluctuates from 2 to around 9.

I'm having the same problem with exact radius search, where points inside the radius aren't always returned, even though the maximum number of points requested hasn't been reached.

Furthermore, setting the checks parameter to 1e3, the same as the size of the dataset, also doesn't resolve the issue. In this case even an approximate search shouldn't terminate before searching the whole dataset. Also, changing the algorithm type to linear or kmeans does provide all the neighbors.

Am I doing something wrong? Can someone try and run the script and reproduce the problem? I'm using matlab r2012a 64bit.

Thanks

The KDTreeIndex from FLANN is optimized for high dimensional search and contains an optimization that makes the results slightly approximate even when the entire tree is explored. For high dimensional points exact search is generally not practical and doing exhaustive search in a kd-tree in general results in worse performance compared to linear search (for high dimensional points).

FLANN contains another kdtree implementation, the KDTreeSingleIndex which is optimized for low dimensional points and which does exact search efficiently. In FLANN 1.7.1 this index was not exposed in the Matlab bindings unfortunately, but you can easily fix that by changing line 9 in flann_build_index.m from

 algos = struct( 'linear', 0, 'kdtree', 1, 'kmeans', 2, 'composite', 3, 'saved', 254, 'autotuned', 255 );

algos = struct( 'linear', 0, 'kdtree', 1, 'kmeans', 2, 'composite', 3, 'kdtree_single', 4, 'saved', 254, 'autotuned', 255 );

or by applying the commit 0a34c3f6bf3a4c797b5bd61c63749992f8a5629e.

After that change the algorithm from 'kdtree' to 'kdtree_single'

flann-lib / flann

MATLAB exact knn problem #76