knnsearch: K-Dimensional Nearest Neighbor Search

In kuwisdelu/matter: Out-of-core statistical computing and signal processing

K-Dimensional Nearest Neighbor Search

Description

Search a matrix of K-dimensional data points and return the indices of the nearest neighbors or of all data points that are within a specified tolerance in each dimension.

Usage

# Nearest neighbor search
knnsearch(x, data, k = 1L, metric = "euclidean", p = 2)

# Range search
kdsearch(x, data, tol = 0, tol.ref = "abs")

# K-D tree
kdtree(data)

Arguments

x	A numeric matrix of coordinates to be matched. Each column should represent a dimension. Each row should be a query point.
data	Either a kdtree object returned by kdtree(), or a numeric matrix of coordinates to search, where each column is a different dimension. If this is missing, then the query x will be used as the data.
k	The number of nearest neighbors to find for each point (row) in x.
metric	Distance metric to use when finding the nearest neighbors. Supported metrics include "euclidean", "maximum", "manhattan", and "minkowski".
p	The power for the Minkowski distance.
tol	The tolerance for finding neighboring points in each dimension. May be a vector with the same length as the number of dimensions. Must be positive.
tol.ref	One of 'abs', 'x', or 'y'. If 'abs', then comparison is done by taking the absolute difference. If either 'x' or 'y', then relative differences are used, and this specifies which to use as the reference (target) value.

Details

knnsearch() performs k-nearest neighbor searches. kdsearch() performs range searches for points within a given tolerance of the query points.

The algorithms are implemented in C and work by building a kd-tree to perform the search. If multiple calls to kdsearch() or knnsearch() are expected on the same data, it can be much faster to build the tree once with kdtree().

A kd-tree is essentially a multidimensional generalization of a binary search tree. Building the search tree is O(n * log n) and searching for a single data point is O(log n).

For knnsearch(), ties are broken based on the original ordering of the rows in data.

Value

For knnsearch(), a matrix with rows equal to the number of rows of x and columns equal to k giving the indices of the k-nearest neighbors.

For kdsearch(), a list with length equal to the number of rows of x, where each list element is a vector of indexes of the matches in data.

Author(s)

Kylie A. Bemis

See Also

bsearch, approx2,

Examples

d <- expand.grid(x=1:10, y=1:10)
x <- rbind(c(1.11, 2.22), c(3.33, 4.44))

knnsearch(x, d, k=3)

kuwisdelu/matter documentation built on Dec. 8, 2024, 8:09 p.m.