jsat.linear.vectorcollection

Class RandomBallCoverOneShot<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.RandomBallCoverOneShot<V>

All Implemented Interfaces:

Serializable, Cloneable, VectorCollection<V>

public class RandomBallCoverOneShot<V extends Vec>
extends Object
implements VectorCollection<V>

An implementation of the on shot search for the Random Ball Cover algorithm. Unlike most algorithms, it attempts to satisfy queries in O(sqrt(n)) time. It does this to be more efficient in its computation and easily parallelizable. Construction time is O(n^3/2).
The one shot algorithm is an approximate nearest neighbor search, and returns the correct nearest neighbor with a certain probability. If an incorrect neighbor is found, it's distance from the true nearest neighbor is bounded.
The RBC algorithm was not originally developed for range queries. While the exact RBC version can perform efficient range queries, the one-shot version is more likely to produce different results, potentially missing a large portion of the vectors that should have been included.

See: Cayton, L. (2012). Accelerating Nearest Neighbor Search on Manycore Systems. 2012 IEEE 26th International Parallel and Distributed Processing Symposium, 402–413. doi:10.1109/IPDPS.2012.45

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RandomBallCoverOneShot.RandomBallCoverOneShotFactory<V extends Vec>

Constructor Summary

Constructors

Constructor and Description
RandomBallCoverOneShot(List<V> vecs, DistanceMetric dm) Creates a new one-shot version of the Random Cover Ball.
RandomBallCoverOneShot(List<V> vecs, DistanceMetric dm, ExecutorService execServ) Creates a new one-shot version of the Random Cover Ball.
RandomBallCoverOneShot(List<V> vecs, DistanceMetric dm, int s) Creates a new one-shot version of the Random Cover Ball.
RandomBallCoverOneShot(List<V> vecs, DistanceMetric dm, int s, ExecutorService execServ) Creates a new one-shot version of the Random Cover Ball.

Method Summary

Modifier and Type	Method and Description
RandomBallCoverOneShot<V>	clone()
List<? extends VecPaired<V,Double>>	search(Vec query, double range) Searches the space for all vectors that are within a given range of the query vector.
List<? extends VecPaired<V,Double>>	search(Vec query, int neighbors) Searches the space for the k neighbors that are closest to the given query vector
int	size() Returns the number of vectors stored in the collection

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomBallCoverOneShot

public RandomBallCoverOneShot(List<V> vecs,
                              DistanceMetric dm,
                              int s,
                              ExecutorService execServ)

Creates a new one-shot version of the Random Cover Ball.

Parameters:

vecs - the vectors to place into the RBC

dm - the distance metric to use

s - the number of points to be claimed by each representative.

execServ - the source of threads for parallel construction

RandomBallCoverOneShot

public RandomBallCoverOneShot(List<V> vecs,
                              DistanceMetric dm,
                              ExecutorService execServ)

Creates a new one-shot version of the Random Cover Ball.

Parameters:

vecs - the vectors to place into the RBC

dm - the distance metric to use

execServ - the source of threads for parallel construction

RandomBallCoverOneShot

public RandomBallCoverOneShot(List<V> vecs,
                              DistanceMetric dm,
                              int s)

Creates a new one-shot version of the Random Cover Ball.

Parameters:

vecs - the vectors to place into the RBC

dm - the distance metric to use

s - the number of points to be claimed by each representative.

RandomBallCoverOneShot

public RandomBallCoverOneShot(List<V> vecs,
                              DistanceMetric dm)

Creates a new one-shot version of the Random Cover Ball.

Parameters:

vecs - the vectors to place into the RBC

dm - the distance metric to use

Method Detail

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  double range)

Description copied from interface: VectorCollection

Searches the space for all vectors that are within a given range of the query vector.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find others near

range - the search range around our query

Returns:

the list of all vectors within the range of our query. The paired value contains the distance to the query vector.

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  int neighbors)

Description copied from interface: VectorCollection

Searches the space for the k neighbors that are closest to the given query vector

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find neighbors of

neighbors - the maximum number of neighbors to return

Returns:

the list the k nearest neighbors, in sorted order from closest to farthest. The paired value contains the distance to the query vector

size

public int size()

Description copied from interface: VectorCollection

Returns the number of vectors stored in the collection

Specified by:

size in interface VectorCollection<V extends Vec>

Returns:

the size of the collection

clone

public RandomBallCoverOneShot<V> clone()

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class Object