jsat.linear.vectorcollection

Class RandomBallCoverOneShot<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.RandomBallCoverOneShot<V>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, VectorCollection<V>

public class RandomBallCoverOneShot<V extends Vec>
extends java.lang.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

See Also:

Serialized Form

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	build(boolean parallel, java.util.List<V> collection, DistanceMetric dm) Builds this metric index from the given collection of points using the given distance metric.
RandomBallCoverOneShot<V>	clone()
V	get(int indx) Accesses a vector from this collection via index.
java.util.List<java.lang.Double>	getAccelerationCache()
DistanceMetric	getDistanceMetric()
void	search(Vec query, double range, java.util.List<java.lang.Integer> neighbors, java.util.List<java.lang.Double> distances) Performs a range search of the current collection.
void	search(Vec query, int numNeighbors, java.util.List<java.lang.Integer> neighbors, java.util.List<java.lang.Double> distances) Performs k-Nearest Neighbor search of the current collection.
void	setDistanceMetric(DistanceMetric dm) Sets the distance metric used for this collection.
int	size() Returns the number of vectors stored in the collection

Methods inherited from class java.lang.Object

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

Methods inherited from interface jsat.linear.vectorcollection.VectorCollection

build, build, build, getVecs, search, search, search, search, search, search

Constructor Detail

RandomBallCoverOneShot

public RandomBallCoverOneShot(java.util.List<V> vecs,
                              DistanceMetric dm,
                              int s,
                              boolean parallel)

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.

parallel - true if construction should be done in parallel, false for single threaded.

RandomBallCoverOneShot

public RandomBallCoverOneShot(java.util.List<V> vecs,
                              DistanceMetric dm,
                              boolean parallel)

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

parallel - true if construction should be done in parallel, false for single threaded.

RandomBallCoverOneShot

public RandomBallCoverOneShot(java.util.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(java.util.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

RandomBallCoverOneShot

public RandomBallCoverOneShot()

Method Detail

build

public void build(boolean parallel,
                  java.util.List<V> collection,
                  DistanceMetric dm)

Description copied from interface: VectorCollection

Builds this metric index from the given collection of points using the given distance metric.

Specified by:

build in interface VectorCollection<V extends Vec>

Parameters:

parallel - true if the index should be built in parallel, or false if it should be done in a single thread.

collection - the list of vectors to put into the index

dm - the distance metric to build the index using.

getAccelerationCache

public java.util.List<java.lang.Double> getAccelerationCache()

Specified by:

getAccelerationCache in interface VectorCollection<V extends Vec>

search

public void search(Vec query,
                   double range,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)

Description copied from interface: VectorCollection

Performs a range search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the point to search for the neighbors within a given radius.

range - the radius to search for all the neighbors with a distance ≤ range.

neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.

distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

search

public void search(Vec query,
                   int numNeighbors,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)

Description copied from interface: VectorCollection

Performs k-Nearest Neighbor search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the point to search for the k-nearest neighbors of

numNeighbors - the number of neighbors k to search for.

neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.

distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

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

get

public V get(int indx)

Description copied from interface: VectorCollection

Accesses a vector from this collection via index.

Specified by:

get in interface VectorCollection<V extends Vec>

Parameters:

indx - the index in [0, VectorCollection.size()) of the vector to access

Returns:

the vector from the collection

clone

public RandomBallCoverOneShot<V> clone()

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class java.lang.Object

setDistanceMetric

public void setDistanceMetric(DistanceMetric dm)

Description copied from interface: VectorCollection

Sets the distance metric used for this collection.

Specified by:

setDistanceMetric in interface VectorCollection<V extends Vec>

Parameters:

dm - the distance metric to use

getDistanceMetric

public DistanceMetric getDistanceMetric()

Specified by:

getDistanceMetric in interface VectorCollection<V extends Vec>

Returns:

the distance metric to use