Categories &

Functions List

Class Definition: ExhaustiveSearcher

Class: ExhaustiveSearcher

Exhaustive nearest neighbor searcher class.

The ExhaustiveSearcher class implements an exhaustive search algorithm for nearest neighbor queries. It stores training data and supports various distance metrics along with their parameter values for performing an exhaustive search. The exhaustive search algorithm computes the distance from each query point to all the points in the training data and facilitates a nearest neighbor search using knnsearch or a radius search using rangesearch.

You can either use the ExhaustiveSearcher class constructor or the createns function to create an ExhaustiveSearcher object.

See also: createns, KDTreeSearcher, hnswSearcher, knnsearch, rangesearch

Source Code: ExhaustiveSearcher

Properties

Parameter for the distance metric, with type and value depending on Distance:

  • For "minkowski", a positive scalar exponent (default 2).
  • For "seuclidean", a nonnegative vector of scaling factors matching the number of columns in X (default is standard deviation of X).
  • For "mahalanobis", a positive definite covariance matrix matching the dimensions of X (default is cov (X)).
  • Empty for other metrics or custom functions.

Distance metric used for searches, specified as a character vector (e.g., "euclidean", "minkowski") or a function handle to a custom distance function. Default is "euclidean". Supported metrics align with those in pdist2.

Training data, specified as an N×P numeric matrix where each row is an observation and each column is a feature. This property is private and cannot be modified after object creation.

Methods

ExhaustiveSearcher: obj = ExhaustiveSearcher (X)
ExhaustiveSearcher: obj = ExhaustiveSearcher (X, name, value)

Create an ExhaustiveSearcher object for nearest neighbor searches.

obj = ExhaustiveSearcher (X) constructs an ExhaustiveSearcher object with training data X using the default "euclidean" distance metric. X must be an N×P numeric matrix, where rows represent observations and columns represent features.

obj = ExhaustiveSearcher (X, name, value) allows customization through name-value pairs:

NameValue
"Distance"Distance metric, specified as a character vector (e.g., "euclidean", "minkowski") or a function handle. Default is "euclidean". See pdist2 for supported metrics.
"P"a positive scalar specifying the exponent for the Minkowski distance. Valid only when "Distance" is "minkowski". Default is 2.
"Scale"a nonnegative vector with the same number of elements as the columns in X specifying the scale parameter for the standardized Euclidean distance. Valid only when "Distance" is "seuclidean". Default is std (X).
"Cov"a positive definite matrix matching the number of columns in X specifying the covariance matrix for the Mahalanobis distance. Valid only when "Distance" is "mahalanobis". Default is cov (X).

See also: ExhaustiveSearcher, knnsearch, rangesearch, pdist2

ExhaustiveSearcher: [idx, D] = knnsearch (obj, Y)
ExhaustiveSearcher: [idx, D] = knnsearch (obj, Y, name, value)

Find the K nearest neighbors in the training data to query points.

[idx, D] = knnsearch (obj, Y) returns the indices idx and distances D of the nearest neighbor in obj.X to each point in Y, using the distance metric specified in obj.Distance.

  • obj is an ExhaustiveSearcher object.
  • Y is an M×P numeric matrix of query points, where P must match the number of columns in obj.X.

[idx, D] = knnsearch (obj, Y, name, value) allows additional options via name-value pairs:

NameValue
"K"A positive integer specifying the number of nearest neighbors to find. Default is 1.
"IncludeTies"Logical flag indicating whether to include all neighbors tied with the Kth smallest distance. Default is false. If true, idx and D are cell arrays.

idx contains the indices of the nearest neighbors in obj.X. D contains the corresponding distances.

See also: ExhaustiveSearcher, rangesearch, pdist2

ExhaustiveSearcher: [idx, D] = rangesearch (obj, Y, r)
ExhaustiveSearcher: [idx, D] = rangesearch (obj, Y, r, name, value)

Find all neighbors within a specified radius of query points.

[idx, D] = rangesearch (obj, Y, r) returns the indices idx and distances D of all points in obj.X within radius r of each point in Y, using the distance metric specified in obj.Distance.

  • obj is an ExhaustiveSearcher object.
  • Y is an M×P numeric matrix of query points, where P must match the number of columns in obj.X.
  • r is a nonnegative scalar specifying the search radius.

[idx, D] = rangesearch (…, name, value) allows additional options via name-value pairs:

NameValue
"SortIndices"Logical flag indicating whether to sort the indices by distance. Default is true.

idx and D are cell arrays where each cell contains the indices and distances for one query point in Y.

See also: ExhaustiveSearcher, knnsearch, pdist2

Example: 1

  

 ## Demo to verify implementation using fisheriris dataset
 load fisheriris
 rng('default');
 numSamples = size (meas, 1);
 queryIndices = [20, 95, 123, 136, 138];
 dataPoints = meas(~ismember (1:numSamples, queryIndices), :);
 queryPoints = meas(queryIndices, :);
 searchModel = ExhaustiveSearcher (dataPoints, 'Distance', 'mahalanobis')
 mahalanobisParam = searchModel.DistParameter
 searchRadius = 3;
 nearestNeighbors = knnsearch (searchModel, queryPoints, "K", 2)
 neighborsInRange = rangesearch (searchModel, queryPoints, searchRadius)

searchModel =

  ExhaustiveSearcher with properties:

                 Distance: 'mahalanobis'
            DistParameter: [4x4 double]
                        X: [145x4 double]
mahalanobisParam =

   0.654708  -0.036803   1.231971   0.502620
  -0.036803   0.191363  -0.322715  -0.119293
   1.231971  -0.322715   3.067148   1.284234
   0.502620  -0.119293   1.284234   0.579984

nearestNeighbors =

     5     6
    98    95
   104   128
   135    65
   102   115

neighborsInRange =
{
  [1,1] =

   Columns 1 through 21:

       5     6    21    46    48    44    37    22     1     8    11    27    26    33    18    12    39     7    40    49    32

   Columns 22 through 42:

      47    19     3    28    29    17    20    43    23    42    16    30     4    56    34    85    24    10    51    38    61

   Columns 43 through 63:

      13    88    14    35    25    78    91    95     2   125    70     9    45    64   134    31    98    36    94   122    15

   Columns 64 through 84:

      96   109    63    66   115    86   145    82   143    77   103   139    74    71    55   124    59   126    65   131    75

   Columns 85 through 98:

      92   102    83    52   110   111    84   100   138    67   119    58    79    89

  [2,1] =

   Columns 1 through 21:

      98    95    83    88    78    89    55    63    69    91    94    90    82    92    59    80   100   138   131    57    66

   Columns 22 through 42:

      67    81    61   125   102   115   145   134    96   110   118   126    93     4    53    64    29    30    72     9    73

   Columns 43 through 63:

      47    79    56    38   107   103   124    42    70    51    14    84    10    12    13    34     3   121   130    71    85

   Columns 64 through 84:

     112     7     8    25    74   120    60   143    24    77    49    39    26   122    54     2    37    58    45     5    97

   Columns 85 through 105:

      86   109     1    27   139   105   101    23   111   142    20    22    18    75    28    40    44    46    52    48    21

   Columns 106 through 121:

      35    65    76   123    62    11    43   132   135    87   119   106     6   127   128   104

  [3,1] =

   Columns 1 through 21:

     104   128   127   106   117   123    58    52    76    50   107    86    74   101    65    75    77   131    96    72    54

   Columns 22 through 35:

      73   115   129    51    63    67    91    71    87   110    92    62   118    82

  [4,1] =

   Columns 1 through 21:

     135    65    75   101   111   117    77    54    50    86   137    52    76   119   141   128    74    71   121   142   143

   Columns 22 through 34:

     136    58   124    51   109   110   104    68    87    96    31    36   139

  [5,1] =

   Columns 1 through 21:

     102   115    91    94    63    56   145    83    88    95    55   131    66    85   122    78    70   103   125    73    98

   Columns 22 through 42:

      84   134   123    51    90   126    67   100   138    61    96   139   110   107    24    44   101    12   106   109    77

   Columns 43 through 63:

      82   130   143    86    59    46    37   104   127    29    69    92    58    72   132    89    99   116   124    52    74

   Columns 64 through 84:

      64     5     8   111     4    30   120    47     7   144   121   118    42   133    39    80    48    32    81    71   119

   Columns 85 through 105:

      27    10     6    54     1    26    75   108    57   128    21     3    65    79    20    11   112    34    50    49   135

   Columns 106 through 109:

      22    38   129     9

}

Example: 2

  

 ## Create an ExhaustiveSearcher with Euclidean distance
 X = [1, 2; 3, 4; 5, 6];
 obj = ExhaustiveSearcher (X);
 ## Find the nearest neighbor to [2, 3]
 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y);
 disp ("Nearest neighbor index:"); disp (idx);
 disp ("Distance:"); disp (D);
 ## Find all points within radius 2
 [idx, D] = rangesearch (obj, Y, 2);
 disp ("Indices within radius:"); disp (idx);
 disp ("Distances:"); disp (D);

Nearest neighbor index:
1
Distance:
1.4142
Indices within radius:
{
  [1,1] =

     1   2

}
Distances:
{
  [1,1] =

     1.4142   1.4142

}

Example: 3

  

 ## Create an ExhaustiveSearcher with Minkowski distance (P=1)
 X = [0, 0; 1, 0; 0, 1];
 obj = ExhaustiveSearcher (X, "Distance", "minkowski", "P", 1);
 ## Find the 2 nearest neighbors to [0.5, 0.5]
 Y = [0.5, 0.5];
 [idx, D] = knnsearch (obj, Y, "K", 2);
 disp ("Nearest neighbor indices:"); disp (idx);
 disp ("Distances:"); disp (D);

Nearest neighbor indices:
   1   2
Distances:
   1   1

Example: 4

  

 rng(42);
 disp('Demonstrating ExhaustiveSearcher');

 n = 100;
 mu1 = [0.3, 0.3];
 mu2 = [0.7, 0.7];
 sigma = 0.1;
 X1 = mu1 + sigma * randn(n/2, 2);
 X2 = mu2 + sigma * randn(n/2, 2);
 X = [X1; X2];

 obj = ExhaustiveSearcher(X);

 Y = [0.3, 0.3; 0.7, 0.7; 0.5, 0.5];

 K = 5;
 [idx, D] = knnsearch(obj, Y, "K", K);

 disp('For the first query point:');
 disp(['Query point: ', num2str(Y(1,:))]);
 disp('Indices of nearest neighbors:');
 disp(idx(1,:));
 disp('Distances:');
 disp(D(1,:));

 figure;
 scatter(X(:,1), X(:,2), 36, 'b', 'filled'); % Training points
 hold on;
 scatter(Y(:,1), Y(:,2), 36, 'r', 'filled'); % Query points
 for i = 1:size(Y,1)
     query = Y(i,:);
     neighbors = X(idx(i,:), :);
     for j = 1:K
         plot([query(1), neighbors(j,1)], [query(2), neighbors(j,2)], 'k-');
     end
 end
 hold off;
 title('K Nearest Neighbors with ExhaustiveSearcher');
 xlabel('X1');
 ylabel('X2');

 r = 0.15;
 [idx, D] = rangesearch(obj, Y, r);

 disp('For the first query point in rangesearch:');
 disp(['Query point: ', num2str(Y(1,:))]);
 disp('Indices of points within radius:');
 disp(idx{1});
 disp('Distances:');
 disp(D{1});

 figure;
 scatter(X(:,1), X(:,2), 36, 'b', 'filled');
 hold on;
 scatter(Y(:,1), Y(:,2), 36, 'r', 'filled');
 theta = linspace(0, 2*pi, 100);
 for i = 1:size(Y,1)
     center = Y(i,:);
     x_circle = center(1) + r * cos(theta);
     y_circle = center(2) + r * sin(theta);
     plot(x_circle, y_circle, 'g-');
     % Highlight points within radius
     if ~isempty(idx{i})
         in_radius = X(idx{i}, :);
         scatter(in_radius(:,1), in_radius(:,2), 36, 'g', 'filled');
     end
 end
 hold off;
 title('Points within Radius with ExhaustiveSearcher');
 xlabel('X1');
 ylabel('X2');

Demonstrating ExhaustiveSearcher
For the first query point:
Query point: 0.3         0.3
Indices of nearest neighbors:
   49   19   14   46   34
Distances:
   0.029932   0.040026   0.046845   0.051107   0.054789
For the first query point in rangesearch:
Query point: 0.3         0.3
Indices of points within radius:
 Columns 1 through 25:

   49   19   14   46   34   23   12   41    1    3   42   48   24    2   11   37   10   27   32   20   44   40   39   21    7

 Columns 26 through 34:

   31   45   30    4   16   47    9   29    8
Distances:
 Columns 1 through 11:

   0.029932   0.040026   0.046845   0.051107   0.054789   0.063517   0.067855   0.071365   0.073769   0.075991   0.082686

 Columns 12 through 22:

   0.084066   0.090008   0.095171   0.096337   0.096836   0.097593   0.098255   0.098948   0.101780   0.108652   0.108983

 Columns 23 through 33:

   0.114272   0.116760   0.120198   0.121721   0.122560   0.127342   0.128062   0.128687   0.130208   0.136007   0.142870

 Column 34:

   0.143009
plotted figure

plotted figure