/*
* Copyright (C) 2017 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.linear.vectorcollection;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.Collectors;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.math.FastMath;
import jsat.utils.BoundedSortedList;
import jsat.utils.DoubleList;
import jsat.utils.IndexTable;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.Pair;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.XORWOW;
/**
* This class implements the Cover-tree algorithm for answering nearest neighbor
* queries. In particular, it uses the "Simplified Cover-tree" algorithm.
* Note, this implementation does not yet support parallel construction.
*
*
* See:
*
* - Beygelzimer, A., Kakade, S., & Langford, J. (2006). Cover trees for
* nearest neighbor. In International Conference on Machine Learning (pp.
* 97–104). New York: ACM. Retrieved from
* here
* - Izbicki, M., & Shelton, C. R. (2015). Faster Cover Trees. In Proceedings
* of the Thirty-Second International Conference on Machine Learning (Vol.
* 37).
*
*
* @author Edward Raff
*/
public final class CoverTree implements IncrementalCollection
{
private DistanceMetric dm;
private List vecs;
private List accell_cache = null;
private TreeNode root = null;
private boolean maxDistDirty = false;
// private boolean nearest_ancestor = false;
private boolean looseBounds = false;
private static final int min_pow_map = -120;
private static final int max_pow_map = 1000;
private static final float[] pow_map = new float[max_pow_map-min_pow_map];
private static final double base = 1.3;
private static final double log2_base = Math.log(base)/Math.log(2);
static
{
for(int pow_indx = min_pow_map; pow_indx < max_pow_map; pow_indx++)
pow_map[pow_indx-min_pow_map] = (float) Math.pow(base, pow_indx);
}
private static double pow(int expo)
{
if(expo >= min_pow_map && expo < max_pow_map)
return pow_map[expo-min_pow_map];
else
return Math.pow(base, expo);
}
public CoverTree(DistanceMetric dm)
{
this.dm = dm;
vecs = new ArrayList<>();
}
public CoverTree(List source, DistanceMetric dm)
{
this(source, dm, false);
}
public CoverTree(List source, DistanceMetric dm, boolean parallel)
{
this(source, dm, parallel, false);
}
public CoverTree(List source, DistanceMetric dm, boolean parallel, boolean looseBounds)
{
setLooseBounds(looseBounds);
build(parallel, source, dm);
}
public CoverTree(CoverTree toCopy)
{
this.dm = toCopy.dm.clone();
this.looseBounds = toCopy.looseBounds;
this.vecs = new ArrayList<>(toCopy.vecs);
if(toCopy.accell_cache != null)
this.accell_cache = new DoubleList(toCopy.accell_cache);
if(toCopy.root != null)
this.root = new TreeNode(toCopy.root);
}
@Override
public List getAccelerationCache()
{
return accell_cache;
}
@Override
public void build(boolean parallel, List collection, DistanceMetric dm)
{
this.dm = dm;
setLooseBounds(looseBounds);
this.vecs = new ArrayList<>(collection);
this.accell_cache = dm.getAccelerationCache(vecs, parallel);
//Cover Tree is sensative to insertion order, so lets make sure its random
IntList order = new IntList(this.vecs.size());
ListUtils.addRange(order, 0, this.vecs.size(), 1);
// Set S = getSet(parallel);
// S.addAll(order);
// int p = S.stream().findAny().get();
// S.remove(p);
//
// this.root = new TreeNode(p);
// construct(parallel, root, S, getSet(parallel), Integer.MAX_VALUE);
Collections.shuffle(order, new XORWOW(54321));
int pos = 0;
for(int i : order)
{
root = simpleInsert(root, i);
pos++;
// System.out.println("\t" + pos + " vs " + this.root.magnitude());
}
// System.out.println(this.vecs.size() + " vs " + this.root.magnitude());
if(!this.looseBounds)//pre-compute all max-dist bounds used during search
{
this.root.maxdist();
Iterator iter = this.root.descendants();
while(iter.hasNext())
{
iter.next().maxdist();
}
}
}
/**
*
* @param p the point p
* @return
*/
private Set construct(boolean parallel, TreeNode p, Set near, Set far, int level)
{
if(near.isEmpty())
return far;
Set workingNearSet;
if(level == Integer.MAX_VALUE)//We need to figure out the correct level and do the split at once to avoid duplicate work
{
int[] points = near.stream().mapToInt(i->i).toArray();
double[] dists = new double[points.length];
double maxDist = ParallelUtils.run(parallel, points.length, (start, end)->
{
double max_ = 0;
for(int i = start; i < end; i++)
{
dists[i] = dm.dist(p.vec_indx, points[i], vecs, accell_cache);
max_ = Math.max(max_, dists[i]);
}
return max_;
}, (a, b) -> Math.max(a, b));
level = p.level = (int) Math.ceil(FastMath.log2(maxDist)/log2_base+1e-4);
p.maxdist = maxDist;
double r_split = pow(p.level-1);
near.clear();
Set newNear = getSet(parallel);
Set newFar = getSet(parallel);
ParallelUtils.run(parallel, points.length, (start, end)->
{
for(int i = start; i < end; i++)
{
double d_i = dists[i];
if(d_i <= r_split)
newNear.add(points[i]);
else if (d_i < 2 * r_split)
newFar.add(points[i]);
else
near.add(points[i]);
}
});
workingNearSet = construct(parallel, p, newNear, newFar, p.level-1);
}
else
{
Pair, Set> pairRet = split(parallel, p.vec_indx, pow(level-1), near);
workingNearSet = construct(parallel, p, pairRet.getFirstItem(), pairRet.getSecondItem(), level-1);
}
while(!workingNearSet.isEmpty())
{
//(i) pick q in NEAR
int q_indx = workingNearSet.stream().findAny().get();
workingNearSet.remove(q_indx);
TreeNode q = new TreeNode(q_indx, level-1);
//(ii) = Construct (q, SPLIT(d(q, ·), 2^(i−1),NEAR,FAR), i−1)
Set unused = construct(parallel, q, workingNearSet, far, level-1);
//(iii) add CHILD to Children(pi)
p.addChild(q);
//(iv) let =SPLIT(d(p, ·), 2^i,UNUSED)
Pair, Set> newPiar = split(parallel, p.vec_indx, pow(level), unused);
Set newNear = newPiar.getFirstItem();
Set newFar = newPiar.getSecondItem();
//(v) add NEW-FAR to FAR, and NEW-NEAR to NEAR.
far.addAll(newFar);
workingNearSet.addAll(newNear);
}
return far;
}
private Pair, Set> split(boolean parallel, int p, double r, Set... S)
{
Set newNear = getSet(parallel);
Set newFar = getSet(parallel);
for(Set S_i : S)
{
int[] toRemove = ParallelUtils.streamP(S_i.stream(), parallel).mapToInt(i->
{
double d_i = dm.dist(p, i, vecs, accell_cache);
if(d_i <= r)
newNear.add(i);
else if(d_i < 2*r)
newFar.add(i);
else
return -1;//-1 will be 'removed' from the set S_i. but -1 isn't a valid index. So no impact
return i;
}).distinct().toArray();
S_i.removeAll(IntList.view(toRemove));
}
return new Pair<>(newNear, newFar);
}
private Set getSet(boolean parallel)
{
Set newNear;
if(parallel)
newNear = ConcurrentHashMap.newKeySet();
else
newNear = new IntSet();
return newNear;
}
@Override
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
@Override
public DistanceMetric getDistanceMetric()
{
return dm;
}
public void setLooseBounds(boolean looseBounds)
{
this.looseBounds = looseBounds;
}
@Override
public void search(Vec query, double range, List neighbors, List distances)
{
neighbors.clear();
distances.clear();
this.root.findNN(range, query, dm.getQueryInfo(query), neighbors, distances, -1.0);
IndexTable it = new IndexTable(distances);
it.apply(distances);
it.apply(neighbors);
}
@Override
public void search(Vec query, int numNeighbors, List neighbors, List distances)
{
// if(maxDistDirty && ! looseBounds)
// {
// this.root.invalidateMaxDist();
// maxDistDirty = false;
// }
BoundedSortedList bsl = new BoundedSortedList<>(numNeighbors);
this.root.findNN(numNeighbors, query, dm.getQueryInfo(query), bsl);
neighbors.clear();
distances.clear();
for(IndexDistPair a : bsl)
{
neighbors.add(a.getIndex());
distances.add(a.getDist());
}
}
@Override
public int size()
{
return vecs.size();
}
@Override
public V get(int indx)
{
return vecs.get(indx);
}
@Override
public CoverTree clone()
{
return new CoverTree<>(this);
}
protected void simpleInsert(V x)
{
int x_indx = this.vecs.size();
this.vecs.add(x);
if(this.accell_cache == null && dm.supportsAcceleration())
this.accell_cache = new DoubleList();
if(this.accell_cache != null)
this.accell_cache.addAll(dm.getQueryInfo(x));
if(this.root == null)//start the tree
{
this.root = new TreeNode(x_indx);
// this.root.setLevel(0);
}
else//actually insert
this.root = simpleInsert(root, x_indx);
}
protected TreeNode simpleInsert(TreeNode p, int x_indx)
{
if(this.root == null)//start the tree
{
this.root = new TreeNode(x_indx);
// this.root.setLevel(0);
return this.root;
}
double p_x_dist = p.dist(x_indx);
if(p_x_dist > p.covdist())//line 1
{
/*
* If the insetion point x has a distance that is SUPER far away,
* the below bound may never hold. Thus, lets detect loops and short
* circuit
*/
final int start_indx = p.vec_indx;
if(p_x_dist - pow(p.level+1) < base*p.covdist())//if this is true, the condition will be true for p AND ALL CHILDREN OF P
while(p_x_dist > base*p.covdist() && !p.isLeaf())//line 2
{
//3: remove any leaf q from p
TreeNode q;
q = p.removeAnyLeaf();
//4: p' = tree with root q and p as only child
TreeNode p_prime = q;
p_prime.addChild(p);
p_prime.fixLevel();
p = p_prime;//5: p = p'
p_x_dist = p.dist(x_indx);
if(p.vec_indx == start_indx)//WE HAVE DONE THIS BEFORE
break;
}
//6: return tree with x as root and p as only child
TreeNode X = new TreeNode(x_indx);
X.addChild(p);
X.fixLevel();
return X;
}
//return insert_(p,x)
return simpleInsert_(p, x_indx);
}
/**
* prerequisites: d(p,x) ≤ covdist(p)
* @param p
* @param x_indx
* @return
*/
protected TreeNode simpleInsert_(TreeNode p, int x_indx)
{
// if(nearest_ancestor)
// {
// double[] dist_to_x = new double[p.numChildren()];
// for(int i = 0; i < dist_to_x.length; i++)
// dist_to_x[i] = p.getChild(i).dist(x_indx);
// IndexTable it = new IndexTable(dist_to_x);
//
// for(int order = 0; order < p.numChildren(); order++) //Line 1:
// {
// int q_indx = it.index(order);
// TreeNode q = p.getChild(q_indx);
// if(q.dist(x_indx) <= q.covdist()) //line 2: d(q,x)≤covdist(q)
// {
// //3: q' ← insert_(q,x)
// TreeNode q_prime = simpleInsert_(q, x_indx);
// //4: p' ← p with child q replaced with q'
// p.replaceChild(q_indx, q_prime);
// //5: return p'
// return p;
// }
// }
// //6: return rebalance(p, x)
// return rebalance(p, x_indx);
// }
// else
{
for(int q_indx = 0; q_indx < p.numChildren(); q_indx++) //Line 1:
{
TreeNode q = p.getChild(q_indx);
if(q.dist(x_indx) <= q.covdist()) //line 2: d(q,x)≤covdist(q)
{
//3: q' ← insert_(q,x)
TreeNode q_prime = simpleInsert_(q, x_indx);
//4: p' ← p with child q replaced with q'
p.replaceChild(q_indx, q_prime);
//5: return p'
return p;
}
}
//6: return p with x added as a child
p.addChild(new TreeNode(x_indx, p.level-1));
return p;
}
}
@Override
public void insert(V x)
{
// maxDistDirty = true;
simpleInsert(x);
}
private class TreeNode implements Cloneable, Serializable
{
TreeNode parent = null;
int level;
int vec_indx;
DoubleList children_dists;
List children;
boolean is_sorted = true;
double maxdist = -1;
public TreeNode(int vec_indx)
{
this(vec_indx, -110);
}
public TreeNode(int vec_indx, int level)
{
this.vec_indx = vec_indx;
this.level = level;
children = new ArrayList<>();
children_dists = new DoubleList();
}
/**
* Copy constructor. Will not copy the parent node. But will copy children nodes and set their parents appropriately.
* @param toCopy
*/
public TreeNode(TreeNode toCopy)
{
this.level = toCopy.level;
this.vec_indx = toCopy.vec_indx;
if(toCopy.children != null)
{
this.children = new ArrayList<>(toCopy.children.size());
this.children_dists = new DoubleList(toCopy.children_dists);
for(TreeNode childToCopy : toCopy.children)
{
TreeNode child = new TreeNode(childToCopy);
child.parent = this;
this.children.add(child);
}
}
this.is_sorted = toCopy.is_sorted;
this.maxdist = toCopy.maxdist;
}
@Override
protected TreeNode clone()
{
return new TreeNode(this);
}
public void invalidateMaxDist()
{
this.maxdist = -1;
for(TreeNode c : children)
c.invalidateMaxDist();
}
public void invalParentMaxdist()
{
this.maxdist = -2;
if(this.parent != null)
this.parent.invalParentMaxdist();
}
public void findNN(int k, Vec query, List x_qi, BoundedSortedList knn)
{
Stack toEval_stack = new Stack<>();
DoubleList dist_to_q_stack = new DoubleList();
{//Quick, add root info to stack for search & prime search Q
double p_x_dist = this.dist(query, x_qi);
dist_to_q_stack.push(p_x_dist);
toEval_stack.push(this);
}
//Search loop
while(!toEval_stack.isEmpty())
{
TreeNode p = toEval_stack.pop();
double p_to_q_dist = dist_to_q_stack.pop();
knn.add(new IndexDistPair(p.vec_indx, p_to_q_dist));
double[] child_query_dist = new double[p.numChildren()];
for(int child_indx = 0; child_indx < p.numChildren(); child_indx++)//compute dists and add to knn while we are at it
{
TreeNode q = p.getChild(child_indx);
child_query_dist[child_indx] = q.dist(query, x_qi);
}
//get them in sorted order
IndexTable it = new IndexTable(child_query_dist);
for(int i_oder = it.length()-1; i_oder >= 0; i_oder--)//reverse order so stack goes in sorted order
{
final int i = it.index(i_oder);
TreeNode q = p.getChild(i);
//4: if d(y,x)>d(y,q)−maxdist(q) then
if(knn.size() < k || knn.last().getDist() > child_query_dist[i] - q.maxdist())
{//Add to the search Q
toEval_stack.push(q);
dist_to_q_stack.push(child_query_dist[i]);
}
}
}
}
//This is the old search code, new code (above) avoids recursion and makes explicit stack
private void findNN_recurse(int k, Vec x, List x_qi, BoundedSortedList knn, double my_dist_to_x)
{
TreeNode p = this;
double p_x_dist;
if(my_dist_to_x < 0)
{
p_x_dist = p.dist(x, x_qi);
}
else
p_x_dist = my_dist_to_x;
knn.add(new IndexDistPair(p.vec_indx, p_x_dist));
//1: if d(p,x)(p_x_dist, vecs.get(p.vec_indx)));//2: y <= p
//3: for each child q of p sorted by *distance to x* do
double[] q_x_dist = new double[p.numChildren()];
for(int q_indx = 0; q_indx < p.numChildren(); q_indx++)//compute dists and add to knn while we are at it
{
TreeNode q = p.getChild(q_indx);
q_x_dist[q_indx] = q.dist(x, x_qi);
//DO NOT ADD DISTANCE TO KNN YET, we will do it recursively
//need to avoid it so bound check below will work propertly
//and otherwise we would double count
// knn.add(new ProbailityMatch(q_x_dist[q_indx], vecs.get(q.vec_indx)));
// q.findNN(k, x, x_qi, knn);
}
//get them in sorted order
IndexTable it = new IndexTable(q_x_dist);
for(int i_oder = 0; i_oder < it.length(); i_oder++)
{
final int i = it.index(i_oder);
TreeNode q = p.getChild(i);
// knn.add(new ProbailityMatch(q_x_dist[i], vecs.get(q.vec_indx)));
//4: if d(y,x)>d(y,q)−maxdist(q) then
// if(knn.size() < k || knn.last().getDist() > q.dist(y_vec, dm.getQueryInfo(y_vec)) - q.maxdist())
if(knn.size() < k || knn.last().getDist() > q_x_dist[i] - q.maxdist())
q.findNN_recurse(k, x, x_qi, knn, q_x_dist[i]);//Line 5:
// else if(q.isLeaf())
// {
// knn.add(new ProbailityMatch(q.dist(x, x_qi), vecs.get(q.vec_indx)));
// }
}
}
public void findNN(double radius, Vec x, List x_qi, List neighbors, List distances, double my_dist_to_x)
{
TreeNode p = this;
double p_x_dist;
if(my_dist_to_x < 0)
{
p_x_dist = p.dist(x, x_qi);
}
else
p_x_dist = my_dist_to_x;
if(p_x_dist <= radius)
{
neighbors.add(p.vec_indx);
distances.add(p_x_dist);
}
//3: for each child q of p , no need to sort b/c radius search
double[] q_x_dist = new double[p.numChildren()];
for(int q_indx = 0; q_indx < p.numChildren(); q_indx++)//compute dists and add to knn while we are at it
{
TreeNode q = p.getChild(q_indx);
q_x_dist[q_indx] = q.dist(x, x_qi);
//DO NOT ADD DISTANCE TO KNN YET, we will do it on recursion
}
//get them in sorted order
for(int i = 0; i < q_x_dist.length; i++)
{
TreeNode q = p.getChild(i);
//4: if d(y,x)>d(y,q)−maxdist(q) then
if(radius > q_x_dist[i] - q.maxdist())
q.findNN(radius, x, x_qi, neighbors, distances, q_x_dist[i]);//Line 5:
}
}
public int magnitude()
{
int count = 1;
for(int i = 0; i < numChildren(); i++)
count += getChild(i).magnitude();
return count;
}
public boolean isLeaf()
{
return this.children == null || this.children.isEmpty();
}
public int numChildren()
{
return this.children.size();
}
public TreeNode getChild(int indx)
{
return this.children.get(indx);
}
public void addChild(TreeNode child)
{
// int new_level = Math.max(this.level, child.level+1);
double dist_to_c = this.dist(child.vec_indx);
// int insert_indx = Collections.binarySearch(children_dists, dist_to_c);
// if(insert_indx < 0)//no exact match, convert to insertion index
// insert_indx = -insert_indx-1;
int insert_indx = this.children.size();
this.children.add(insert_indx, child);
this.children_dists.add(insert_indx, dist_to_c);
// child.setLevel(new_level-1);
// this.setLevel(new_level);
this.fixChildrenLevel();
// this.maxdist = -1;//no logner valid, so clear it
this.invalParentMaxdist();
}
public void replaceChild(int orig_index, TreeNode child)
{
double dist_to_c = this.dist(child.vec_indx);
this.children.set(orig_index, child);
this.children_dists.set(orig_index, dist_to_c);
// child.setLevel(new_level-1);
// this.setLevel(new_level);
// this.maxdist = -1;//no logner valid, so clear it
this.fixChildrenLevel();
this.invalParentMaxdist();
// this.children.remove(orig_index);
// this.children_dists.removeD(orig_index);
// this.addChild(child);
// int new_level = Math.max(this.level, child.level+1);
// this.children.set(orig_index, child);
// this.children_dists.set(orig_index, this.dist(child.vec_indx));
// child.setLevel(new_level-1);
// this.setLevel(new_level);
}
public void removeChild(int orig_index)
{
this.children.remove(orig_index);
this.children_dists.remove(orig_index);
// this.fixChildrenLevel();
this.invalParentMaxdist();
}
/**
* Removes a descendant of this node that is a leaf node.
* @return the descendant that was removed
*/
public TreeNode removeAnyLeaf()
{
if(this.isLeaf())
throw new RuntimeException("BUG: node has no children to rmeove");
//lets just grab the furthest child?
TreeNode child = children.get(children.size()-1);
if(child.isLeaf())
{
child.invalParentMaxdist();
children.remove(children.size()-1);
children_dists.remove(children_dists.size()-1);
return child;
}
else//need to remove one of child's descentants to get a leaf
{
return child.removeAnyLeaf();
}
}
public double dist(TreeNode q)
{
return dm.dist(this.vec_indx, q.vec_indx, vecs, accell_cache);
}
public double dist(int x_indx)
{
return dm.dist(this.vec_indx, x_indx, vecs, accell_cache);
}
public double dist(Vec x, List qi)
{
return dm.dist(this.vec_indx, x, qi, vecs, accell_cache);
}
public void setLevel(int level)
{
// if(this.level == level)
// return;//levels are already set correctly
this.level = level;
// for(TreeNode q : children)
// q.setLevel(level-1);
}
public void fixLevel()
{
// double maxDist = Math.pow(1.3, -110);
double maxDist = pow(-110);
for(int i = 0; i < numChildren(); i++)
maxDist = Math.max(maxDist, this.children_dists.getD(i));
// this.level = (int) Math.ceil(Math.log(maxDist)/Math.log(1.3));
this.level = (int) Math.ceil(FastMath.log2(maxDist)/log2_base+1e-4);
fixChildrenLevel();
}
public void fixChildrenLevel()
{
for(int i = 0; i < numChildren(); i++)
{
TreeNode c = getChild(i);
if(this.level-1 != c.level)
{
c.level = this.level-1;
c.fixChildrenLevel();
}
}
}
public double covdist()
{
// return Math.pow(1.3, level);
return pow(level);
}
public double sepdist()
{
// return Math.pow(1.3, level-1);
return pow(level-1);
}
private double maxdist()
{
if(isLeaf())
return 0;
if(looseBounds)
return pow(level+1);
if (this.maxdist >= 0)
return maxdist;
//else, maxdist = -1, indicating we need to compute it
Stack toGetChildrenFrom = new Stack<>();
toGetChildrenFrom.add(this);
while(!toGetChildrenFrom.empty())
{
TreeNode runner = toGetChildrenFrom.pop();
for(int q_indx = 0; q_indx < runner.numChildren(); q_indx++)
{
TreeNode q = runner.getChild(q_indx);
maxdist = Math.max(maxdist, this.dist(q.vec_indx));//TODO can optimize for first set of childern, we already have that
toGetChildrenFrom.add(q);
}
}
return maxdist;
}
private Iterator descendants()
{
final Stack toIterate = new Stack<>();
toIterate.addAll(children);
Iterator iter = new Iterator()
{
@Override
public boolean hasNext()
{
return !toIterate.isEmpty();
}
@Override
public TreeNode next()
{
TreeNode next = toIterate.pop();
toIterate.addAll(next.children);
return next;
}
@Override
public void remove()
{
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
};
return iter;
}
}
}
Ads help maintain this website.