package jsat.linear.vectorcollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.BoundedSortedList;
import jsat.utils.DoubleList;
import jsat.utils.FakeExecutor;
import jsat.utils.IndexTable;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.concurrent.ParallelUtils;
/**
* 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(n3/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
*/
public class RandomBallCoverOneShot implements VectorCollection
{
private static final long serialVersionUID = -2562499883847452797L;
private DistanceMetric dm;
private List> ownedVecs;
private List R;
private List allVecs;
private List distCache;
/**
* The number of points each representative will consider
*/
private int s;
/**
* Distance from representative i to its farthest neighbor it owns
*/
double[] repRadius;
/**
* Creates a new one-shot version of the Random Cover Ball.
* @param vecs the vectors to place into the RBC
* @param dm the distance metric to use
* @param s the number of points to be claimed by each representative.
* @param parallel {@code true} if construction should be done in parallel,
* {@code false} for single threaded.
*/
public RandomBallCoverOneShot(List vecs, DistanceMetric dm, int s, boolean parallel)
{
this.s = s;
build(parallel, vecs, dm);
}
/**
* Creates a new one-shot version of the Random Cover Ball.
* @param vecs the vectors to place into the RBC
* @param dm the distance metric to use
* @param parallel {@code true} if construction should be done in parallel,
* {@code false} for single threaded.
*/
public RandomBallCoverOneShot(List vecs, DistanceMetric dm, boolean parallel)
{
this(vecs, dm, (int)Math.sqrt(vecs.size()), parallel);
}
/**
* Creates a new one-shot version of the Random Cover Ball.
* @param vecs the vectors to place into the RBC
* @param dm the distance metric to use
* @param s the number of points to be claimed by each representative.
*/
public RandomBallCoverOneShot(List vecs, DistanceMetric dm, int s)
{
this(vecs, dm, s, false);
}
/**
* Creates a new one-shot version of the Random Cover Ball.
* @param vecs the vectors to place into the RBC
* @param dm the distance metric to use
*/
public RandomBallCoverOneShot(List vecs, DistanceMetric dm)
{
this(vecs, dm, (int)Math.sqrt(vecs.size()));
}
public RandomBallCoverOneShot()
{
this.dm = new EuclideanDistance();
this.s = -1;
}
/**
* Copy constructor
* @param other the RandomBallCover to create a copy of
*/
private RandomBallCoverOneShot(RandomBallCoverOneShot other)
{
this.dm = other.dm.clone();
this.ownedVecs = new ArrayList<>(other.ownedVecs.size());
for(int i = 0; i < other.ownedVecs.size(); i++)
{
this.ownedVecs.add(new IntList(other.ownedVecs.get(i)));
}
this.R = new IntList(other.R);
this.repRadius = Arrays.copyOf(other.repRadius, other.repRadius.length);
this.s = other.s;
if(other.distCache != null)
this.distCache = new DoubleList(other.distCache);
if(other.allVecs != null)
this.allVecs = new ArrayList<>(other.allVecs);
}
@Override
public void build(boolean parallel, List collection, DistanceMetric dm)
{
this.allVecs = new ArrayList<>(collection);
distCache = dm.getAccelerationCache(collection, parallel);
IntList allIndices = new IntList(allVecs.size());
ListUtils.addRange(allIndices, 0, allVecs.size(), 1);
if(s < 0)
s = (int) Math.sqrt(allVecs.size());
setUp(allIndices, parallel);
}
private void setUp(List allIndices, boolean parallel)
{
int repCount = (int) Math.max(1, Math.sqrt(allIndices.size()));
Collections.shuffle(allIndices);
R = allIndices.subList(0, repCount);
repRadius = new double[R.size()];
final List allRemainingVecs = allIndices.subList(repCount, allIndices.size());
ownedVecs = new ArrayList<>(repCount);
for (int i = 0; i < repCount; i++)
{
ownedVecs.add(new IntList(s));
}
ParallelUtils.run(parallel, R.size(), (i)->
{
final int Ri = R.get(i);
final List ROwned = ownedVecs.get(i);
BoundedSortedList nearest = new BoundedSortedList<>(s);
for(int v : allRemainingVecs)
nearest.add(new IndexDistPair(v, dm.dist(v, Ri, allVecs, distCache)));
for(IndexDistPair pmv : nearest)
ROwned.add(pmv.getIndex());
});
}
@Override
public List getAccelerationCache()
{
return distCache;
}
@Override
public void search(Vec query, double range, List neighbors, List distances)
{
neighbors.clear();
distances.clear();
List qi = dm.getQueryInfo(query);
//Find the best representative r_q
double tmp;
double bestDist = Double.POSITIVE_INFINITY;
int bestRep = 0;
for (int i = 0; i < R.size(); i++)
{
if ((tmp = dm.dist(R.get(i), query, qi, allVecs, distCache) ) < bestDist)
{
bestRep = i;
bestDist = tmp;
}
if(tmp <= range)
{
neighbors.add(R.get(i));
distances.add(tmp);
}
}
for (int v : ownedVecs.get(bestRep))
if((tmp = dm.dist(v, query, qi, allVecs, distCache) ) <= range)
{
neighbors.add(v);
distances.add(tmp);
}
IndexTable it = new IndexTable(distances);
it.apply(neighbors);
it.apply(distances);
}
@Override
public void search(Vec query, int numNeighbors, List neighbors, List distances)
{
neighbors.clear();
distances.clear();
BoundedSortedList knn =
new BoundedSortedList<>(numNeighbors);
List qi = dm.getQueryInfo(query);
//Find the best representative r_q
double tmp;
double bestDist = Double.POSITIVE_INFINITY;
int bestRep = 0;
for (int i = 0; i < R.size(); i++)
if ((tmp = dm.dist(R.get(i), query, qi, allVecs, distCache) ) < bestDist)
{
bestRep = i;
bestDist = tmp;
}
knn.add(new IndexDistPair(R.get(bestRep), bestDist));
for (int v : ownedVecs.get(bestRep))
knn.add(new IndexDistPair(v, dm.dist(v, query, qi, allVecs, distCache)));
for(IndexDistPair v : knn)
{
neighbors.add(v.getIndex());
distances.add(v.getDist());
}
}
@Override
public int size()
{
return R.size()*s;
}
@Override
public V get(int indx)
{
return allVecs.get(indx);
}
@Override
public RandomBallCoverOneShot clone()
{
return new RandomBallCoverOneShot<>(this);
}
@Override
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
@Override
public DistanceMetric getDistanceMetric()
{
return dm;
}
}
Ads help maintain this website.