API Reference / algorithms / neighbors / search /

brute_force.py

Linear (Brute Force) Nearest Neighbor Search.

Classes

BruteForceSearch

class algorithms.neighbors.search.brute_force.BruteForceSearch(NearestNeighborSearch)

Linear (brute force) nearest neighbor search via exhaustive distance computation.

This algorithm computes the distance from the query point to all points in the training dataset. While simple and always exact, its query time scales linearly with the number of training samples, making it the baseline against which tree-based methods are compared.
Constructor 
__init__(
    self,
)

Overview

The algorithm operates in the following steps:

  1. Store all training points during build().
  2. For a query, compute the squared Euclidean distance to every
training point using a vectorized expansion: \|q - x_i\|^2 = \|q\|^2 + \|x_i\|^2 - 2 q^T x_i.
  1. Use argpartition to efficiently find the k smallest
distances in O(n) time.
  1. Sort only the k selected neighbors by distance.

Theory

The distance metric is Euclidean distance:

d(q, x_i) = \sqrt{\sum_{j=1}^{m} (q_j - x_{i,j})^2}

Using the expansion \|a - b\|^2 = \|a\|^2 + \|b\|^2 - 2 a^T b allows the computation to leverage optimized BLAS matrix-vector products, yielding a constant-factor speedup over a naive loop.

Attributes

X_
np.ndarray
The training data stored for search.
n_samples_
int
Number of training samples.
n_features_
int
Number of features in the training data.

Notes

Complexity:

  • Construction: O(1) (data is simply stored)
  • Query: O(n \cdot m) per query point, where n = samples, m = features
  • Space: O(n \cdot m) for the stored training data
When to use BruteForceSearch:
  • Small datasets where tree construction overhead is not justified
  • High-dimensional data where tree-based pruning provides little benefit
  • As a correctness baseline to verify tree-based search results
  • One-off queries where amortizing construction cost is not possible

References

Knuth1973
Knuth, D.E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.

See Also

KDTree

Axis-aligned tree, faster in low dimensions.
BallTree

Spherical partitions, better in moderate to high dimensions.

Build a brute-force search and find the nearest neighbor:

python 
>>> from tuiml.algorithms.neighbors.search import BruteForceSearch
>>> import numpy as np
>>> X = np.array([[1, 2], [3, 4], [5, 6]])
>>> search = BruteForceSearch()
>>> search.build(X)
BruteForceSearch(n_samples=3)
>>> dists, indices = search.query([3.1, 4.1], k=1)

Methods

__init__ (self)

Initialize BruteForceSearch.

build (self, X: np.ndarray) -> 'BruteForceSearch'

Store the training data for brute force search.

Parameters
X
np.ndarray of shape (n_samples, n_features)
The training data.
Returns
self
BruteForceSearch
Returns the instance itself.
query (self, x: np.ndarray, k: int=1) -> Tuple[np.ndarray, np.ndarray]

Find the k nearest neighbors for a query point.

Parameters
x
np.ndarray of shape (n_features,)
The query point.
k
int = 1
Number of neighbors to find.
Returns
distances
np.ndarray of shape (k,)
Distances to the k nearest neighbors.
indices
np.ndarray of shape (k,)
Indices of the k nearest neighbors in the training data.
query_batch (self, X: np.ndarray, k: int=1) -> Tuple[np.ndarray, np.ndarray]

Find the k nearest neighbors for multiple query points.

Parameters
X
np.ndarray of shape (n_queries, n_features)
The query points.
k
int = 1
Number of neighbors to find.
Returns
distances
np.ndarray of shape (n_queries, k)
Distances to the k nearest neighbors.
indices
np.ndarray of shape (n_queries, k)
Indices of the k nearest neighbors in the training data.
query_radius (self, x: np.ndarray, radius: float) -> Tuple[np.ndarray, np.ndarray]

Find all neighbors within a specified radius.

Parameters
x
np.ndarray of shape (n_features,)
The query point.
radius
float
The maximum distance to search within.
Returns
distances
np.ndarray
Distances to all neighbors within the radius.
indices
np.ndarray
Indices of neighbors within the radius.
__repr__ (self) -> str

String representation.