smile.neighbor

Class LinearSearch<T>

java.lang.Object

smile.neighbor.LinearSearch<T>

Type Parameters:

T - the type of data objects.

All Implemented Interfaces:

KNNSearch<T,T>, NearestNeighborSearch<T,T>, RNNSearch<T,T>

public class LinearSearch<T>
extends java.lang.Object
implements NearestNeighborSearch<T,T>, KNNSearch<T,T>, RNNSearch<T,T>

Brute force linear nearest neighbor search. This simplest solution computes the distance from the query point to every other point in the database, keeping track of the "best so far". There are no search data structures to maintain, so linear search has no space complexity beyond the storage of the database. Although it is very simple, naive search outperforms space partitioning approaches (e.g. K-D trees) on higher dimensional spaces.

By default, the query object (reference equality) is excluded from the neighborhood. You may change this behavior with setIdenticalExcluded. Note that you may observe weird behavior with String objects. JVM will pool the string literal objects. So the below variables String a = "ABC"; String b = "ABC"; String c = "AB" + "C"; are actually equal in reference test a == b == c. With toy data that you type explicitly in the code, this will cause problems. Fortunately, the data would be read from secondary storage in production.

Constructor Summary

Constructors

Constructor and Description
LinearSearch(T[] dataset, Distance<T> distance) Constructor.

Method Summary

Modifier and Type	Method and Description
boolean	isIdenticalExcluded() Get whether if query object self be excluded from the neighborhood.
Neighbor<T,T>[]	knn(T q, int k) Search the k nearest neighbors to the query.
Neighbor<T,T>	nearest(T q) Search the nearest neighbor to the given sample.
void	range(T q, double radius, java.util.List<Neighbor<T,T>> neighbors) Search the neighbors in the given radius of query object, i.e.
LinearSearch<T>	setIdenticalExcluded(boolean excluded) Set if exclude query object self from the neighborhood.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinearSearch

public LinearSearch(T[] dataset,
                    Distance<T> distance)

Constructor. By default, query object self will be excluded from search.

Method Detail

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

setIdenticalExcluded

public LinearSearch<T> setIdenticalExcluded(boolean excluded)

Set if exclude query object self from the neighborhood.

isIdenticalExcluded

public boolean isIdenticalExcluded()

Get whether if query object self be excluded from the neighborhood.

nearest

public Neighbor<T,T> nearest(T q)

Description copied from interface: NearestNeighborSearch

Search the nearest neighbor to the given sample.

Specified by:

nearest in interface NearestNeighborSearch<T,T>

Parameters:

q - the query key.

Returns:

the nearest neighbor

knn

public Neighbor<T,T>[] knn(T q,
                           int k)

Description copied from interface: KNNSearch

Search the k nearest neighbors to the query.

Specified by:

knn in interface KNNSearch<T,T>

Parameters:

q - the query key.

k - the number of nearest neighbors to search for.

range

public void range(T q,
                  double radius,
                  java.util.List<Neighbor<T,T>> neighbors)

Description copied from interface: RNNSearch

Search the neighbors in the given radius of query object, i.e. d(q, v) ≤ radius.

Specified by:

range in interface RNNSearch<T,T>

Parameters:

q - the query key.

radius - the radius of search range from target.

neighbors - the list to store found neighbors in the given range on output.