bbTreeSearch

BB (branch-and-bound) tree search for 1 nearest neighbor

Contents

Syntax

Description

[nnIndex, nnDist, distCompCount] = bbTreeSearch(vec, bbTree, allData) returns the 1 nearest neighbor via BB (branch-and-bound) tree search

• vec: test input vector
• bbTree: tree structure generated by bbTreeGen, with the following fields:
  • bbTree(i).mean: mean vector of a tree node
  • bbTree(i).radius: radius vector of a tree node
  • bbTree(i).child: indices of children for a non-terminal node
  • bbTree(i).dataIndex: indices of data for a terminal node
  • bbTree(i).dist2mean: distance to mean of a terminal node
• allData: all sample data points
• nnIndex: index of the nearest neighbor
• nnDist: distance to the nearest neighbor
• distCompCount: no. of distance computation

Example

dim=2;
dataNum=1000;
testNum=100;
data=rand(dim, dataNum);
testData=rand(dim, testNum);
clusterNum=3;
level=4;
plotOpt=1;
bbTree=bbTreeGen(data, clusterNum, level, plotOpt);
for i=1:testNum
	[nnIndex(i), nnDist(i), distCompCount(i)] = bbTreeSearch(testData(:,i), bbTree, data);
end
distMat=distPairwise(data, testData);
[minValue, minIndex]=min(distMat);
fprintf('isequal(nnIndex, minIndex)=%d\n', isequal(nnIndex, minIndex));
plot(distCompCount, '.-');
xlabel('Test case indices'); ylabel('Distance computation count');
title(sprintf('Average number of distance computation = %f\n', mean(distCompCount)));

isequal(nnIndex, minIndex)=1

See Also

bbTreeGen.

Published with MATLAB® R2018a