/*
* Copyright (C) 2018 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.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.IntStream;
import jsat.clustering.MEDDIT;
import jsat.clustering.PAM;
import jsat.clustering.TRIKMEDS;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
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.AtomicDoubleArray;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* This class implements the Ball Tree algorithm for accelerating nearest
* neighbor queries. Contained within this class are multiple methods of
* building Ball Trees. Options for changing construction can alter the method
* of {@link ConstructionMethod construction} of the hierarchy is made, or how
* {@link PivotSelection pivot} is selected.
* The default method of construction and pivot selection for ball trees will
* work for most cases, but is not appicable for all distance metrics. If you
* are using an exotic distance metric the
* {@link BallTree.ConstructionMethod#TOP_DOWN_FARTHEST} and
* {@link PivotSelection#MEDOID} will work for any dataset, but may be
* slower.
*
* See:
*
* - Omohundro, S. M. (1989). Five Balltree Construction Algorithms (No.
* TR-89-063).
* - Moore, A. W. (2000). The Anchors Hierarchy: Using the Triangle Inequality
* to Survive High Dimensional Data. In Proceedings of the Sixteenth Conference
* on Uncertainty in Artificial Intelligence (pp. 397–405). San Francisco, CA,
* USA: Morgan Kaufmann Publishers Inc. Retrieved from
* here
*
*
* @author Edward Raff
* @param
*/
public class BallTree implements IncrementalCollection, DualTree
{
public static final int DEFAULT_LEAF_SIZE = 40;
private int leaf_size = DEFAULT_LEAF_SIZE;
private DistanceMetric dm;
private List allVecs;
private List cache;
private ConstructionMethod construction_method;
private PivotSelection pivot_method;
private Node root;
@Override
public IndexNode getRoot()
{
return root;
}
@Override
public List getAccelerationCache()
{
return cache;
}
public enum ConstructionMethod
{
/**
* This represents a top-down construction approach, that can be used
* for any distance metric. At each branch the children are given
* initial prototypes. The left child has a prototype selected as the
* point farthest from the pivot, and the right child the point farthest
* from the left's. The points are split based on which prototype thye
* are closest too. The process continues recursively.
*
* See: Moore, A. W. (2000). The Anchors Hierarchy: Using the Triangle
* Inequality to Survive High Dimensional Data. In Proceedings of the
* Sixteenth Conference on Uncertainty in Artificial Intelligence (pp.
* 397–405). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
* Retrieved from http://dl.acm.org/citation.cfm?id=2073946.2073993 for
* details.
*/
TOP_DOWN_FARTHEST,
/**
* This represents a top-down construction approach similar to a
* KD-tree's construction. It requires a metric where it has access to
* meaningful feature values. At each node, the dimension with the
* largest spread in values is selected. Then the split is made based on
* sorting the found feature into two even halves.
* See: Omohundro, S. M. (1989). Five Balltree Construction Algorithms
* (No. TR-89-063).
*/
KD_STYLE,
/**
* This represents a "middle-out" construction approach. Computational
* is works best when the {@link PivotSelection#CENTROID centroid} pivot
* selection method can be used.
* See: Moore, A. W. (2000). The Anchors Hierarchy: Using the Triangle
* Inequality to Survive High Dimensional Data. In Proceedings of the
* Sixteenth Conference on Uncertainty in Artificial Intelligence (pp.
* 397–405). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
* Retrieved from http://dl.acm.org/citation.cfm?id=2073946.2073993 for
* details.
*/
ANCHORS_HIERARCHY;
}
public enum PivotSelection
{
/**
* This method selects the pivot by taking the centroid (average) of all
* the data within a node. This method may not be applicable for all
* metrics, and can't be used for once for which there is no computable
* average.
*/
CENTROID
{
@Override
public Vec getPivot(boolean parallel, List points, List extends Vec> data, DistanceMetric dm, List cache)
{
if (points.size() == 1)
return data.get(points.get(0)).clone();
Vec pivot = new DenseVector(data.get(points.get(0)).length());
for (int i : points)
pivot.mutableAdd(data.get(i));
pivot.mutableDivide(points.size());
return pivot;
}
},
/**
* This method selects the pivot by searching for the medoid of the
* data. This can be used in all circumstances, but may be slower.
*/
MEDOID
{
@Override
public Vec getPivot(boolean parallel, List points, List extends Vec> data, DistanceMetric dm, List cache)
{
if (points.size() == 1)
return data.get(points.get(0)).clone();
int indx;
if(dm.isValidMetric())
indx = TRIKMEDS.medoid(parallel, points, data, dm, cache);
else
indx = PAM.medoid(parallel, points, data, dm, cache);
return data.get(indx);
}
},
/**
* This method selects the pivot by searching for an approximate medoid
* of the data. This can be used in all circumstances, but may be
* slower.
*/
MEDOID_APRX
{
@Override
public Vec getPivot(boolean parallel, List points, List extends Vec> data, DistanceMetric dm, List cache)
{
if (points.size() == 1)
return data.get(points.get(0)).clone();
int indx;
//Faster to use exact search
if(points.size() < 1000)
{
if(dm.isValidMetric())
indx = TRIKMEDS.medoid(parallel, points, data, dm, cache);
else
indx = PAM.medoid(parallel, points, data, dm, cache);
}
else//Lets do approx search
indx = MEDDIT.medoid(parallel, points, 0.2, data, dm, cache);
return data.get(indx);
}
},
/**
* A random point will be selected as the pivot for the ball
*/
RANDOM
{
@Override
public Vec getPivot(boolean parallel, List points, List extends Vec> data, DistanceMetric dm, List cache)
{
int indx = RandomUtil.getLocalRandom().nextInt(points.size());
return data.get(indx);
}
},;
public abstract Vec getPivot(boolean parallel, List points, List extends Vec> data, DistanceMetric dm, List cache);
}
public BallTree()
{
this(new EuclideanDistance(), ConstructionMethod.KD_STYLE, PivotSelection.CENTROID);
}
public BallTree(DistanceMetric dm, ConstructionMethod method, PivotSelection pivot_method)
{
setConstruction_method(method);
setPivot_method(pivot_method);
setDistanceMetric(dm);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public BallTree(BallTree toCopy)
{
this(toCopy.dm, toCopy.construction_method, toCopy.pivot_method);
if(toCopy.allVecs != null)
this.allVecs = new ArrayList<>(toCopy.allVecs);
if(toCopy.cache != null)
this.cache = new DoubleList(toCopy.cache);
if(toCopy.root != null)
this.root = cloneChangeContext(toCopy.root);
this.leaf_size = toCopy.leaf_size;
}
@Override
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
@Override
public DistanceMetric getDistanceMetric()
{
return dm;
}
/**
* Sets the number of points stored within a leaf node of the index. Larger
* values avoid search overhead, but reduce opportunities for pruning.
*
* @param leaf_size the size of a leaf node. Must be at least 2
*/
public void setLeafSize(int leaf_size)
{
if (leaf_size < 2)
throw new IllegalArgumentException("The leaf size must be >= 2 to support all splitting methods");
this.leaf_size = leaf_size;
}
/**
*
* @return the number of points to store within a leaf node
*/
public int getLeafSize()
{
return leaf_size;
}
/**
* Computes the maximum depth of the current tree. A value of zero indicates
* that only a root node exists or the tree is empty. Any other value is the
* maximum number of children a node contains.
*
* @return the maximum current depth of this Ball Tree
*/
public int getMaxDepth()
{
if(root == null)
return 0;
else
return root.findMaxDepth(0);
}
public void setPivot_method(PivotSelection pivot_method)
{
this.pivot_method = pivot_method;
}
public PivotSelection getPivot_method()
{
return pivot_method;
}
public void setConstruction_method(ConstructionMethod construction_method)
{
this.construction_method = construction_method;
}
public ConstructionMethod getConstruction_method()
{
return construction_method;
}
private Node build_far_top_down(List points, boolean parallel)
{
Branch branch = new Branch();
branch.setPivot(points);
branch.setRadius(points);
//Use point farthest from parent pivot for left child
int f1 = ParallelUtils.streamP(points.stream(), parallel)
.map(i->new IndexDistPair(i, dm.dist(i, branch.pivot, branch.pivot_qi, allVecs, cache)))
.max(IndexDistPair::compareTo).orElse(new IndexDistPair(0, 0.0)).indx;
//use point farhter from f1 for right child
int f2 = ParallelUtils.streamP(points.stream(), parallel)
.map(i->new IndexDistPair(i, dm.dist(i, f1, allVecs, cache)))
.max(IndexDistPair::compareTo).orElse(new IndexDistPair(1, 0.0)).indx;
//Now split children based on who is closes to f1 and f2
IntList left_children = new IntList();
IntList right_children = new IntList();
for(int p : points)
{
double d_f1 = dm.dist(p, f1, allVecs, cache);
double d_f2 = dm.dist(p, f2, allVecs, cache);
if(d_f1 < d_f2)
left_children.add(p);
else
right_children.add(p);
}
if(left_children.isEmpty() || right_children.isEmpty())
{
//This can happen if all the points have the exact same value, so all distances are zero.
//So we can't branch, return a leaf node instead
left_children.addAll(right_children);
Leaf leaf = new Leaf(left_children);
leaf.pivot = branch.pivot;
leaf.pivot_qi = branch.pivot_qi;
leaf.radius = 0.0;//Weird, but correct! All dists = 0, so radius = 0
return leaf;
}
//everyone has been assigned, now creat children objects
branch.left_child = build(left_children, parallel);
branch.right_child = build(right_children, parallel);
branch.left_child.parent = branch;
branch.right_child.parent = branch;
return branch;
}
private Node build_kd(List points, boolean parallel)
{
//Lets find the dimension with the maximum spread
int D = allVecs.get(0).length();
final boolean isSparse = allVecs.get(0).isSparse();
//If sparse, keep a set of indexes we HAVE NOT SEEN
//these have implicity zeros we need to add back at the end
final Set neverSeen;
if (isSparse)
if (parallel)
{
neverSeen = ConcurrentHashMap.newKeySet();
ListUtils.addRange(neverSeen, 0, D, 1);
}
else
neverSeen = new IntSet(ListUtils.range(0, D));
else
neverSeen = Collections.EMPTY_SET;
AtomicDoubleArray mins = new AtomicDoubleArray(D);
mins.fill(Double.POSITIVE_INFINITY);
AtomicDoubleArray maxs = new AtomicDoubleArray(D);
maxs.fill(Double.NEGATIVE_INFINITY);
ParallelUtils.streamP(points.stream(), parallel).forEach(i->
{
for(IndexValue iv : get(i))
{
int d = iv.getIndex();
mins.updateAndGet(d, (m_d)->Math.min(m_d, iv.getValue()));
maxs.updateAndGet(d, (m_d)->Math.max(m_d, iv.getValue()));
neverSeen.remove(d);
}
});
IndexDistPair maxSpread = ParallelUtils.range(D, parallel)
.mapToObj(d->
{
double max_d = maxs.get(d), min_d = mins.get(d);
if(neverSeen != null && neverSeen.contains(d))
{
max_d = Math.max(max_d, 0);
min_d = Math.min(min_d, 0);
}
return new IndexDistPair(d, max_d - min_d);
})
.max(IndexDistPair::compareTo).get();
if(maxSpread.dist == 0)//all the data is the same? Return a leaf
{
Leaf leaf = new Leaf(new IntList(points));
leaf.setPivot(points);
leaf.setRadius(points);
return leaf;
}
//We found it! Lets sort points by this new value
final int d = maxSpread.indx;
points.sort((Integer o1, Integer o2) -> Double.compare(get(o1).get(d), get(o2).get(d)));
int midPoint = points.size()/2;
//Lets check that we don't have identical values, and adjust as needed
while(midPoint > 1 && get(midPoint-1).get(d) == get(midPoint).get(d))
midPoint--;
List left_children = points.subList(0, midPoint);
List right_children = points.subList(midPoint, points.size());
Branch branch = new Branch();
branch.setPivot(points);
branch.setRadius(points);
//everyone has been assigned, now creat children objects
branch.left_child = build(left_children, parallel);
branch.right_child = build(right_children, parallel);
branch.left_child.parent = branch;
branch.right_child.parent = branch;
return branch;
}
private Node build_anchors(List points, boolean parallel)
{
//Ceiling to avoid issues with points rounding down to k=1, causing an infinite recusion
int K = (int) Math.ceil(Math.sqrt(points.size()));
int[] anchor_point_index = new int[K];
int[] anchor_index = new int[K];
IntList[] owned = new IntList[K];
//anchor paper says sort from hight dist to low, we do reverse for convience and removal efficiancy
DoubleList[] ownedDist = new DoubleList[K];
for(int k = 1; k < K; k++)
{
owned[k] = new IntList();
ownedDist[k] = new DoubleList();
}
Random rand = RandomUtil.getRandom();
//First case is special, select anchor at random and create list
anchor_point_index[0] =rand.nextInt(points.size());
anchor_index[0] = points.get(anchor_point_index[0]);
owned[0] = IntList.range(points.size());
ownedDist[0] = DoubleList.view(ParallelUtils.streamP(owned[0].streamInts(), parallel)
.mapToDouble(i->dm.dist(anchor_index[0], points.get(i), allVecs, cache))
.toArray(),
points.size());
IndexTable it = new IndexTable(ownedDist[0]);
it.apply(owned[0]);
it.apply(ownedDist[0]);
//Now lets create the other anchors
for(int k = 1; k < K; k++)
{
/*
* How is the new anchor a^new chosen? We simply find the current
* anchor a^maxrad with the largest radius, and choose the pivot of
* a^new to be the point owned by a^maxrad that is furthest from
* a^maxrad
*/
int max_radius_anch = IntStream.range(0, k).mapToObj(z-> new IndexDistPair(z, ownedDist[z].get(ownedDist[z].size()-1)))
.max(IndexDistPair::compareTo)
.get().indx;
anchor_point_index[k] = owned[max_radius_anch].getI(owned[max_radius_anch].size()-1);
anchor_index[k] = points.get(anchor_point_index[k]);
owned[max_radius_anch].remove(owned[max_radius_anch].size()-1);
ownedDist[max_radius_anch].remove(ownedDist[max_radius_anch].size()-1);
owned[k].add(anchor_point_index[k]);
ownedDist[k].add(0.0);
//lets go through other anchors and see what we can steal
for(int j = 0; j < k; j++)
{
double dist_ak_aj = dm.dist(anchor_index[j], anchor_index[k], allVecs, cache);
ListIterator ownedIter = owned[j].listIterator(owned[j].size());
ListIterator ownedDistIter = ownedDist[j].listIterator(ownedDist[j].size());
while(ownedIter.hasPrevious())
{
int point_indx = ownedIter.previous();
double dist_aj_x = ownedDistIter.previous();
double dist_ak_x = dm.dist(anchor_index[k], points.get(point_indx), allVecs, cache);
if(dist_ak_x < dist_aj_x)//we can steal this point!
{
owned[k].add(point_indx);
ownedDist[k].add(dist_ak_x);
ownedIter.remove();
ownedDistIter.remove();
}
else if(dist_ak_x < dist_ak_aj/2)
{
//"we can deduce that the remainder of the points in ai's list cannot possibly be stolen"
break;
}
}
}
//now sort our new children
it = new IndexTable(ownedDist[k]);
it.apply(owned[k]);
it.apply(ownedDist[k]);
}
//Now we have sqrt(R) anchors. Lets do the middle-down first, creating Nodes for each anchor
List anchor_nodes = new ArrayList<>();
for (int k = 0; k < K; k++)
{
Node n_k = build(IntList.view(owned[k].streamInts().map(i->points.get(i)).toArray()), parallel);
n_k.pivot = get(anchor_index[k]);
n_k.radius = ownedDist[k].getD(ownedDist[k].size()-1);
anchor_nodes.add(n_k);
}
//TODO below code is ugly... needs improvement
//Ok, now lets go middle-up to finish the tree
//We will store the costs of merging any pair of anchor_nodes in this map
Map, Double> mergeCost = new HashMap<>();
Map, Vec> pivotCache = new HashMap<>();
//use a priority queue to pop of workers, and use values from mergeCost to sort
List>> mergeQs = new ArrayList<>();
PriorityQueue QQ = new PriorityQueue<>((q1, q2)->
{
double v1 = mergeCost.get(mergeQs.get(q1).peek());
double v2 = mergeCost.get(mergeQs.get(q2).peek());
return Double.compare(v1, v2);
});
///Initial population of Qs and costs
for(int k = 0; k < K; k++)
{
PriorityQueue> mergeQ_k = new PriorityQueue<>((Pair o1, Pair o2) ->
Double.compare(mergeCost.get(o1), mergeCost.get(o2)));
mergeQs.add(mergeQ_k);
Node n_k = anchor_nodes.get(k);
IntList owned_nk = new IntList();
for(int i : n_k)
owned_nk.add(i);
int size_k = owned_nk.size();
for(int z = k+1; z < K; z++)
{
Node n_z = anchor_nodes.get(z);
Pair p = new Pair<>(k, z);
IntList owned_nkz = new IntList(owned_nk);
int size_z, size_nk;
for(int i : n_z)
owned_nkz.add(i);
size_nk = owned_nkz.size();
size_z = size_nk-size_k;
Vec pivot_candidate;
if(pivot_method == PivotSelection.CENTROID)
{
//we can directly compute the would-be pivot
pivot_candidate = n_k.pivot.clone();
pivot_candidate.mutableMultiply(size_k/(double)size_nk);
pivot_candidate.mutableAdd(size_z/(double)size_nk, n_z.pivot);
}
else//we need to compute the pivot
pivot_candidate = pivot_method.getPivot(parallel, owned_nkz, allVecs, dm, cache);
List pivor_candidate_qi = dm.getQueryInfo(pivot_candidate);
//what would the radius be?
double radius_kz = 0;
for(int i : owned_nkz)
radius_kz = Math.max(radius_kz, dm.dist(i, pivot_candidate, pivor_candidate_qi, allVecs, cache));
mergeCost.put(p, radius_kz);
pivotCache.put(p, pivot_candidate);
mergeQ_k.add(p);
}
if(!mergeQ_k.isEmpty())
QQ.add(k);
}
//Now lets start merging!
Branch toReturn = null;
while(!QQ.isEmpty())
{
int winningQ = QQ.poll();
Pair toMerge = mergeQs.get(winningQ).poll();
int other = toMerge.getSecondItem();
if(anchor_nodes.get(winningQ) == null)//leftover, its gone
continue;
else if(anchor_nodes.get(other) == null)
{
if(!mergeQs.get(winningQ).isEmpty())//stale, lets fix
QQ.add(winningQ);
continue;
}
Branch merged = toReturn = new Branch();
merged.pivot = pivotCache.get(toMerge);
merged.pivot_qi = dm.getQueryInfo(merged.pivot);
merged.radius = mergeCost.get(toMerge);
merged.left_child = anchor_nodes.get(winningQ);
merged.right_child = anchor_nodes.get(other);
merged.left_child.parent = merged;
merged.right_child.parent = merged;
anchor_nodes.set(winningQ, merged);
anchor_nodes.set(other, null);
//OK, we have merged two points. Now book keeping. Remove all Qs
PriorityQueue> mergeQ_k = new PriorityQueue<>((Pair o1, Pair o2) ->
Double.compare(mergeCost.get(o1), mergeCost.get(o2)));
mergeQs.set(winningQ, mergeQ_k);
Node n_k = merged;
IntList owned_nk = new IntList();
for(int i : n_k)
owned_nk.add(i);
int size_k = owned_nk.size();
for(int z = 0; z < anchor_nodes.size(); z++)
{
if(z == winningQ)
continue;
if(anchor_nodes.get(z) == null)
continue;
Node n_z = anchor_nodes.get(z);
Pair p;
if(winningQ < z)
p = new Pair<>(winningQ, z);
else
p = new Pair<>(z, winningQ);
IntList owned_nkz = new IntList(owned_nk);
int size_z, size_nk;
for(int i : n_z)
owned_nkz.add(i);
size_nk = owned_nkz.size();
size_z = size_nk-size_k;
Vec pivot_candidate;
if(pivot_method == PivotSelection.CENTROID)
{
//we can directly compute the would-be pivot
pivot_candidate = n_k.pivot.clone();
pivot_candidate.mutableMultiply(size_k/(double)size_nk);
pivot_candidate.mutableAdd(size_z/(double)size_nk, n_z.pivot);
}
else//we need to compute the pivot
pivot_candidate = pivot_method.getPivot(parallel, owned_nkz, allVecs, dm, cache);
List pivor_candidate_qi = dm.getQueryInfo(pivot_candidate);
//what would the radius be?
double radius_kz = 0;
for(int i : owned_nkz)
radius_kz = Math.max(radius_kz, dm.dist(i, pivot_candidate, pivor_candidate_qi, allVecs, cache));
pivotCache.put(p, pivot_candidate);
if(winningQ < z)
{
mergeCost.put(p, radius_kz);
mergeQ_k.add(p);
}
else
{
mergeQs.get(z).remove(p);
mergeCost.put(p, radius_kz);
mergeQs.get(z).add(p);
}
}
if(!mergeQ_k.isEmpty())
QQ.add(winningQ);
}
return toReturn;
}
private Node build(List points, boolean parallel)
{
//universal base case
if(points.size() <= leaf_size)
{
Leaf leaf = new Leaf(new IntList(points));
leaf.setPivot(points);
leaf.setRadius(points);
return leaf;
}
switch(construction_method)
{
case ANCHORS_HIERARCHY:
return build_anchors(points, parallel);
case KD_STYLE:
return build_kd(points, parallel);
case TOP_DOWN_FARTHEST:
return build_far_top_down(points, parallel);
}
return new Leaf(new IntList(0));
}
@Override
public void build(boolean parallel, List collection, DistanceMetric dm)
{
this.allVecs = new ArrayList<>(collection);
setDistanceMetric(dm);
this.cache = dm.getAccelerationCache(allVecs, parallel);
this.root = build(IntList.range(collection.size()), parallel);
}
@Override
public void insert(V x)
{
if(root == null)
{
allVecs = new ArrayList<>();
allVecs.add(x);
cache = dm.getAccelerationCache(allVecs);
root = new Leaf(IntList.range(1));
root.pivot = x.clone();
root.pivot_qi = dm.getQueryInfo(x);
root.radius = 0;
return;
}
int indx = allVecs.size();
allVecs.add(x);
if(cache != null)
cache.addAll(dm.getQueryInfo(x));
Branch parentNode = null;
Node curNode = root;
double dist_to_curNode = dm.dist(indx, curNode.pivot, curNode.pivot_qi, allVecs, cache);
while(curNode != null)
{
curNode.radius = Math.max(curNode.radius, dist_to_curNode);
if(curNode instanceof jsat.linear.vectorcollection.BallTree.Leaf)
{
Leaf lroot = (Leaf) curNode;
lroot.children.add(indx);
if(lroot.children.size() > leaf_size)
{
Node newNode = build(lroot.children, false);
if(parentNode == null)//We are the root node and a leaf
root = newNode;
else if(parentNode.left_child == curNode)//YES, intentinoally checking object equality
parentNode.left_child = newNode;
else
parentNode.right_child = newNode;
}
return;
}
else
{
Branch b = (Branch) curNode;
double left_dist = dm.dist(indx, b.left_child.pivot, b.left_child.pivot_qi, allVecs, cache);
double right_dist = dm.dist(indx, b.right_child.pivot, b.right_child.pivot_qi, allVecs, cache);
boolean goLeftBranch;
goLeftBranch = left_dist < right_dist;
//decend tree
parentNode = b;
if(goLeftBranch)
{
curNode = b.left_child;
dist_to_curNode = left_dist;
}
else
{
curNode = b.right_child;
dist_to_curNode = right_dist;
}
}
}
}
@Override
public BallTree clone()
{
return new BallTree<>(this);
}
@Override
public void search(Vec query, double range, List neighbors, List distances)
{
neighbors.clear();
distances.clear();
root.search(query, dm.getQueryInfo(query), range, neighbors, distances);
IndexTable it = new IndexTable(distances);
it.apply(distances);
it.apply(neighbors);
}
@Override
public void search(Vec query, int numNeighbors, List neighbors, List distances)
{
neighbors.clear();
distances.clear();
BoundedSortedList knn = new BoundedSortedList<>(numNeighbors);
root.search(query, dm.getQueryInfo(query), numNeighbors, knn, Double.POSITIVE_INFINITY);
for(IndexDistPair p : knn)
{
neighbors.add(p.indx);
distances.add(p.dist);
}
}
@Override
public V get(int indx)
{
return allVecs.get(indx);
}
@Override
public int size()
{
return allVecs.size();
}
private abstract class Node implements Cloneable, Serializable, Iterable, IndexNode
{
Vec pivot;
List pivot_qi;
double radius;
Node parent;
double parrent_dist = Double.POSITIVE_INFINITY;
public Node()
{
}
public Node(Node toCopy)
{
if(toCopy.pivot != null)
this.pivot = toCopy.pivot.clone();
if(toCopy.pivot_qi != null)
this.pivot_qi = new DoubleList(toCopy.pivot_qi);
this.radius = toCopy.radius;
}
public void setPivot(List points)
{
if(points.size() == 1)
pivot = get(points.get(0)).clone();
else
pivot = pivot_method.getPivot(false, points, allVecs, dm, cache);
pivot_qi = dm.getQueryInfo(pivot);
}
public void setRadius(List points)
{
this.radius = 0;
for(int i : points)
radius = Math.max(radius, dm.dist(i, pivot, pivot_qi, allVecs, cache));
}
abstract public int findMaxDepth(int curDepth);
abstract public void search(Vec query, List qi, double range, List neighbors, List distances);
abstract public void search(Vec query, List qi, int numNeighbors, BoundedSortedList knn, double pivot_to_query);
@Override
public double minNodeDistance(int other)
{
return 0;
}
@Override
public double minNodeDistance(Node other)
{
return dm.dist(this.pivot, other.pivot) - this.radius - other.radius;
}
@Override
public double furthestDescendantDistance()
{
return radius;
}
@Override
public double maxNodeDistance(Node other)
{
return dm.dist(this.pivot, other.pivot) + this.radius + other.radius;
}
@Override
public double[] minMaxDistance(Node other)
{
double d = dm.dist(this.pivot, other.pivot);
return new double[]
{
d - this.radius - other.radius,
d + this.radius + other.radius
};
}
@Override
public double furthestPointDistance()
{
return 0;//don't own any points, so dist is zero
}
@Override
public Node getParrent()
{
return parent;
}
// @Override
// public double getParentDistance()
// {
// return parrent_dist;
// }
@Override
public Vec getVec(int indx)
{
return get(indx);
}
}
private class Leaf extends Node
{
IntList children;
public Leaf(IntList children)
{
this.children = children;
}
public Leaf(Leaf toCopy)
{
super(toCopy);
this.children = new IntList(toCopy.children);
}
@Override
public void search(Vec query, List qi, double range, List neighbors, List distances)
{
for(int indx : children)
{
double dist = dm.dist(indx, query, qi, allVecs, cache);
if(dist <= range)
{
neighbors.add(indx);
distances.add(dist);
}
}
}
@Override
public void search(Vec query, List qi, int numNeighbors, BoundedSortedList knn, double pivot_to_query)
{
for(int indx : children)
knn.add(new IndexDistPair(indx, dm.dist(indx, query, qi, allVecs, cache)));
}
@Override
public Iterator iterator()
{
return children.iterator();
}
@Override
public int findMaxDepth(int curDepth)
{
return curDepth;
}
@Override
public int numChildren()
{
return 0;
}
@Override
public IndexNode getChild(int indx)
{
throw new IndexOutOfBoundsException("Leaf nodes do not have children");
}
@Override
public int numPoints()
{
return children.size();
}
@Override
public int getPoint(int indx)
{
return children.get(indx);
}
}
private class Branch extends Node
{
Node left_child;
Node right_child;
public Branch()
{
}
public int findMaxDepth(int curDepth)
{
return Math.max(left_child.findMaxDepth(curDepth+1), right_child.findMaxDepth(curDepth+1));
}
public Branch(Branch toCopy)
{
super(toCopy);
this.left_child = cloneChangeContext(toCopy.left_child);
this.right_child = cloneChangeContext(toCopy.right_child);
}
@Override
public void search(Vec query, List qi, double range, List neighbors, List distances)
{
if(dm.dist(query, pivot) - radius >= range)
return;//We can prune this branch!
left_child.search(query, qi, range, neighbors, distances);
right_child.search(query, qi, range, neighbors, distances);
}
@Override
public void search(Vec query, List qi, int numNeighbors, BoundedSortedList knn, double pivot_to_query)
{
if(Double.isInfinite(pivot_to_query))//can happen for first call
pivot_to_query = dm.dist(query, pivot);
if(knn.size() >= numNeighbors && pivot_to_query - radius >= knn.last().dist)
return;//We can prune this branch!
double dist_left = dm.dist(query, left_child.pivot);
double dist_right = dm.dist(query, right_child.pivot);
double close_child_dist = dist_left;
Node close_child = left_child;
double far_child_dist = dist_right;
Node far_child = right_child;
if(dist_right < dist_left)
{
close_child_dist = dist_right;
close_child = right_child;
far_child_dist = dist_left;
far_child = left_child;
}
close_child.search(query, qi, numNeighbors, knn, close_child_dist);
far_child.search(query, qi, numNeighbors, knn, far_child_dist);
}
@Override
public Iterator iterator()
{
Iterator iter_left = left_child.iterator();
if(right_child == null)
System.out.println("AWD?");
Iterator iter_right = right_child.iterator();
return new Iterator()
{
@Override
public boolean hasNext()
{
return iter_left.hasNext() || iter_right.hasNext();
}
@Override
public Integer next()
{
if(iter_left.hasNext())
return iter_left.next();
else
return iter_right.next();
}
};
}
@Override
public int numChildren()
{
return 2;
}
@Override
public IndexNode getChild(int indx)
{
switch(indx)
{
case 0:
return left_child;
case 1:
return right_child;
default:
throw new IndexOutOfBoundsException();
}
}
@Override
public int numPoints()
{
return 0;
}
@Override
public int getPoint(int indx)
{
throw new IndexOutOfBoundsException("Branching node does not contain any children");
}
}
private Node cloneChangeContext(Node toClone)
{
if (toClone != null)
if (toClone instanceof jsat.linear.vectorcollection.BallTree.Leaf)
return new Leaf((Leaf) toClone);
else
return new Branch((Branch) toClone);
return null;
}
}
Ads help maintain this website.