package jsat.linear.vectorcollection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.utils.*;
import static java.lang.Math.*;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.concurrent.ParallelUtils;

/**
 * An implementation of the exact 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). 
* Unlike the original paper, which assumes single queries will be run in * parallel, the algorithm has been modified to perform additional pruning and * to support range queries. *

* 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 RandomBallCover implements IncrementalCollection { private static final long serialVersionUID = 2437771973228849200L; private DistanceMetric dm; /** * The indices match with their representatives in R */ private List> ownedVecs; /** * The indices match with their representatives in R and in ownedVecs. Each * value indicates the distance of the point to its owner. They are not in * any order */ private List ownedRDists; /** * The list of representatives */ private List R; private int size; private List allVecs; private List distCache; /** * Distance from representative i to its farthest neighbor it owns */ private double[] repRadius; /** * Creates a new Random Ball Cover * @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 RandomBallCover(List vecs, DistanceMetric dm, boolean parallel) { this.dm = dm; build(parallel, vecs, dm); } /** * Creates a new Random Ball Cover * @param vecs the vectors to place into the RBC * @param dm the distance metric to use */ public RandomBallCover(List vecs, DistanceMetric dm) { this(vecs, dm, false); } public RandomBallCover(DistanceMetric dm) { this.dm = dm; this.size = 0; this.allVecs = new ArrayList<>(); if(dm.supportsAcceleration()) this.distCache = new DoubleList(); this.R = new IntList(); } public RandomBallCover() { this(new EuclideanDistance()); } /** * Copy constructor * @param other the RandomBallCover to create a copy of */ private RandomBallCover(RandomBallCover other) { this.dm = other.dm.clone(); this.size = other.size; if(other.allVecs != null) this.allVecs = new ArrayList<>(other.allVecs); if(other.distCache != null) this.distCache = new DoubleList(other.distCache); if(other.ownedVecs != null) this.ownedVecs = new ArrayList<>(other.ownedVecs.size()); if(other.ownedRDists != null) this.ownedRDists = new ArrayList<>(other.ownedRDists.size()); if(other.ownedRDists != null) for(int i = 0; i < other.ownedRDists.size(); i++) { this.ownedRDists.add(new DoubleList(other.ownedRDists.get(i))); this.ownedVecs.add(new IntList(other.ownedVecs.get(i))); } this.R = new IntList(other.R); if(other.repRadius != null) this.repRadius = Arrays.copyOf(other.repRadius, other.repRadius.length); } @Override public void build(boolean parallel, List collection, DistanceMetric dm) { setDistanceMetric(dm); this.size = collection.size(); this.allVecs = new ArrayList<>(collection); this.distCache = dm.getAccelerationCache(allVecs, parallel); IntList allIndices = new IntList(allVecs.size()); ListUtils.addRange(allIndices, 0, size, 1); setUp(allIndices, parallel); } @Override public List getAccelerationCache() { return distCache; } private void setUp(List vecIndices, boolean parallel) { int repCount = (int) Math.max(1, Math.sqrt(vecIndices.size())); Collections.shuffle(vecIndices); R = new IntList(vecIndices.subList(0, repCount)); repRadius = new double[R.size()]; ownedRDists = new ArrayList<>(repRadius.length); IntList vecIndicesSub = new IntList(vecIndices.subList(repCount, vecIndices.size())); ownedVecs = new ArrayList<>(repCount); for (int i = 0; i < repCount; i++) { ownedVecs.add(new IntList(repCount)); ownedRDists.add(new DoubleList(repCount)); } ParallelUtils.run(parallel, vecIndicesSub.size(), (start, end)-> { double tmp; for (int v : vecIndicesSub.subList(start, end)) { int bestRep = 0; double bestDist = dm.dist(v, R.get(0), allVecs, distCache); for (int potentialRep = 1; potentialRep < R.size(); potentialRep++) if ((tmp = dm.dist(v, R.get(potentialRep), allVecs, distCache)) < bestDist) { bestDist = tmp; bestRep = potentialRep; } synchronized (ownedVecs.get(bestRep)) { ownedVecs.get(bestRep).add(v); ownedRDists.get(bestRep).add(bestDist); repRadius[bestRep] = Math.max(repRadius[bestRep], bestDist); } } }); } @Override public void search(Vec query, double range, List neighbors, List distances) { neighbors.clear(); distances.clear(); List qi = dm.getQueryInfo(query); if(repRadius == null)//brute force search b/c small collection { for(int i = 0; i < allVecs.size(); i++) { double dist = dm.dist(i, query, qi, allVecs, distCache); if(dist <= range) { distances.add(dist); neighbors.add(i); } } return; } //Find the best representative r_q, and add its owned children to knn list. double[] queryRDists = new double[R.size()]; for (int i = 0; i < R.size(); i++) if ((queryRDists[i] = dm.dist(R.get(i), query, qi, allVecs, distCache)) <= range) { neighbors.add(R.get(i)); distances.add(queryRDists[i]); } IndexTable sorted = new IndexTable(queryRDists); //k-nn search through the rest of the data set for (int i_indx = 0; i_indx < R.size(); i_indx++) { int i = sorted.index(i_indx); //Prune our representatives that are just too far if (queryRDists[i] > range + repRadius[i]) continue; //Add any new nn imediatly, hopefully shrinking the bound before //the next representative is tested double dist; for (int j = 0; j < ownedVecs.get(i).size(); j++) { double rDist = ownedRDists.get(i).getD(j); if (queryRDists[i] > range + rDist)//first inqueality on a per point basis continue; if ((dist = dm.dist(ownedVecs.get(i).get(j), query, qi, allVecs, distCache)) <= range) { neighbors.add(ownedVecs.get(i).get(j)); distances.add(dist); } } } IndexTable it = new IndexTable(distances); it.apply(neighbors); it.apply(distances); } @Override public void search(Vec query, int numNeighbors, List neighbors, List distances) { BoundedSortedList knn = new BoundedSortedList<>(numNeighbors); neighbors.clear(); distances.clear(); List qi = dm.getQueryInfo(query); if(repRadius == null)//brute force search b/c small collection { for(int i = 0; i < allVecs.size(); i++) knn.add(new IndexDistPair(i, dm.dist(i, query, qi, allVecs, distCache))); } else { //Find the best representative r_q, and add its owned children to knn list. double[] queryRDists = new double[R.size()]; Arrays.fill(queryRDists, Double.MAX_VALUE); int bestRep = 0; for (int i = 0; i < R.size(); i++) if ((queryRDists[i] = dm.dist(R.get(i), query, qi, allVecs, distCache)) < queryRDists[bestRep]) bestRep = i; //Other cluster reps R will get a chance to be added to the list later knn.add(new IndexDistPair(R.get(bestRep), queryRDists[bestRep])); //need k'th nearest representative R for bounds check IndexTable it = new IndexTable(queryRDists); int kth_best_rept; if(numNeighbors < R.size())//need the k'th closest, but if less than K we can't sure that bound kth_best_rept = it.index(numNeighbors-1); else//You are asking for too many neighbors, we can't use the 2nd bound kth_best_rept = -1;//if somone uses this we will get an IndexOutOfBound, telling us about the bug! for (int v : ownedVecs.get(bestRep)) knn.add(new IndexDistPair(v, dm.dist(v, query, qi, allVecs, distCache))); //k-nn search through the rest of the data set for (int sorted_order = 1; sorted_order < R.size(); sorted_order++) {//start at 1 b/c we brute forced the closest rep first final int i = it.index(sorted_order); if(knn.size() == numNeighbors)//no prunnig until we reach k-nns { //Prune out representatives that are just too far if (queryRDists[i] > knn.last().getDist() + repRadius[i]) continue; //check to make sure we can use this bound before attempting else if (kth_best_rept >= 0 && queryRDists[i] > 3 * queryRDists[kth_best_rept]) continue; } //Add any new nn imediatly, hopefully shrinking the bound before //the next representative is tested knn.add(new IndexDistPair(R.get(i), queryRDists[i])); final List L_i_index = ownedVecs.get(i); final DoubleList L_i_radius = ownedRDists.get(i); for (int j = 0; j < ownedVecs.get(i).size(); j++) { double rDist = L_i_radius.getD(j); //Check the first inequality on a per point basis if (knn.size() == numNeighbors && queryRDists[i] > knn.last().getDist() + rDist) continue; int indx = L_i_index.get(j); V v = allVecs.get(indx); knn.add(new IndexDistPair(indx, dm.dist(indx, query, qi, allVecs, distCache))); } } } for(IndexDistPair v : knn) { neighbors.add(v.getIndex()); distances.add(v.getDist()); } } @Override public void insert(V x) { final int new_indx = allVecs.size(); allVecs.add(x); List qi = dm.getQueryInfo(x); if(distCache != null) distCache.addAll(qi); size++; if(size < 10)//brute force for now { R.add(new_indx);//use R for brute force return; } else if(repRadius == null)//initial normal build { R.add(new_indx); setUp(new IntList(R), false); return; } //else, normal addition //Find the best representative double[] queryRDists = new double[R.size()]; Arrays.fill(queryRDists, Double.MAX_VALUE); int bestRep = 0; for (int i = 0; i < R.size(); i++) if ((queryRDists[i] = dm.dist(R.get(i), x, qi, allVecs, distCache)) < queryRDists[bestRep]) bestRep = i; //Add new point and update information ownedVecs.get(bestRep).add(new_indx); ownedRDists.get(bestRep).add(queryRDists[bestRep]); repRadius[bestRep] = Math.max(repRadius[bestRep], queryRDists[bestRep]); if(pow(ceil(sqrt(size)), 2) != size) return;//we are done //else, expand R set int new_r_vec_indx = -1; {//lets randomly sample a point that isn't a rep int ran_val = new Random().nextInt(size-R.size()-1); int R_pos = 0; while(ran_val >= 0) { if(ran_val >= ownedVecs.get(R_pos).size()) ran_val -= ownedVecs.get(R_pos++).size(); else//found the list to grab from { new_r_vec_indx = ownedVecs.get(R_pos).remove(ran_val); ownedRDists.get(R_pos).remove(ran_val); //update radius repRadius[R_pos] = 0; for(double d : ownedRDists.get(R_pos)) repRadius[R_pos] = Math.max(repRadius[R_pos], d); //stop loop break; } } } //We now have a new rep, we need to find the people it will own double max_radius = 0; for(double d : repRadius) max_radius = Math.max(max_radius, d); IntList potentialChildIndx = new IntList(); DoubleList potentialChildDist = new DoubleList(); search(get(new_r_vec_indx), max_radius, potentialChildIndx, potentialChildDist); //add new R to set after to avoid search issues repRadius = Arrays.copyOf(repRadius, repRadius.length+1); R.add(new_r_vec_indx); ownedRDists.add(new DoubleList()); ownedVecs.add(new IntList()); final int r_new = R.size()-1; /* * Existing structure of RBC bookkeping dosn't lend itself to the insertion case. * B/c the R set expansion is rare, we don't modify that internal structure. * Instead, we will create a new temporary strucutre to store things * based on the index of the data point. This gives us easy direct * indexing ability. We then fix-up the RBC structure at the end. */ int[] whoOwnsMe = new int[allVecs.size()]; Arrays.fill(whoOwnsMe, -1); double[] distToMyOwner = new double[allVecs.size()]; for (int i = 0; i < R.size() - 1; i++)//technicaly this is O(n), but its really fast - so who cares { List L_ry = ownedVecs.get(i); for (int j = 0; j < L_ry.size(); j++) { whoOwnsMe[L_ry.get(j)] = i; distToMyOwner[L_ry.get(j)] = ownedRDists.get(i).getD(j); } } boolean[] R_is_dirty = new boolean[R.size()]; Arrays.fill(R_is_dirty, false); R_is_dirty[r_new] = true; for(int i = 0; i < potentialChildIndx.size(); i++) { double d_y_r_new = potentialChildDist.getD(i); int y_indx = potentialChildIndx.getI(i); //find who owns y_indx int r_y = whoOwnsMe[y_indx]; if(r_y == -1)//Represantative, skip continue; double d_y_ry = distToMyOwner[y_indx]; if(d_y_ry > d_y_r_new)//change ownership { R_is_dirty[r_y] = true; whoOwnsMe[y_indx] = r_new; distToMyOwner[y_indx] = d_y_r_new; } } //update representative radi for (int r_indx = 0; r_indx < R.size(); r_indx++) if(R_is_dirty[r_indx])//clear vecs so we can re-populate { repRadius[r_indx] = 0; ownedRDists.get(r_indx).clear(); ownedVecs.get(r_indx).clear(); } for(int i = 0; i < whoOwnsMe.length; i++) { int r_i = whoOwnsMe[i]; if(r_i == -1)//Represantative, skip continue; if(R_is_dirty[r_i]) { repRadius[r_i] = Math.max(repRadius[r_i], distToMyOwner[i]); ownedRDists.get(r_i).add(distToMyOwner[i]); ownedVecs.get(r_i).add(i); } } } @Override public int size() { return size; } @Override public V get(int indx) { return allVecs.get(indx); } @Override public RandomBallCover clone() { return new RandomBallCover<>(this); } @Override public void setDistanceMetric(DistanceMetric dm) { this.dm = dm; } @Override public DistanceMetric getDistanceMetric() { return dm; } }

Ads help maintain this website.