/*
* 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 static java.lang.Math.*;
import java.util.ArrayList;
import java.util.List;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.utils.BoundedSortedList;
import jsat.utils.DoubleList;
import jsat.utils.IndexTable;
import jsat.utils.IntList;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.function.BiFunction;
import jsat.utils.ListUtils;
/**
*
* @author Edward Raff
* @param
*/
public interface DualTree extends VectorCollection
{
public IndexNode getRoot();
@Override
public DualTree clone();
default public double dist(int self_index, int other_index, DualTree other)
{
return getDistanceMetric().dist(this.get(self_index), other.get(self_index));
}
@Override
public void search(Vec query, int numNeighbors, List neighbors, List distances);
@Override
default public void search(VectorCollection VC, int numNeighbors, List> neighbors, List> distances, boolean parallel )
{
if(!(VC instanceof DualTree))
{
VectorCollection.super.search(VC, numNeighbors, neighbors, distances, parallel);
return;
}
DualTree Q = (DualTree) VC;
//Mpa each node to a cached value. This is used for recursive bound updates
Map query_B_cache = parallel ? new ConcurrentHashMap<>(Q.size()) : new HashMap<>(Q.size());
//For each item in Q, we want to find its nearest neighbor in THIS collection.
//each item in Q gets a priority queue of k-nns
List> allPriorities = new ArrayList<>();
for(int i = 0; i < Q.size(); i++)
allPriorities.add(new BoundedSortedList<>(numNeighbors));
///For simplicity and fast calculations, lets combine acceleration caches into one view
final List this_cache = this.getAccelerationCache();
final List other_cache = Q.getAccelerationCache();
final int N_r = this.size();
final List wholeCache = this_cache == null ? null : ListUtils.mergedView(this_cache, other_cache);
final List allVecs = new ArrayList<>(N_r+Q.size());
for(int i = 0; i < N_r; i++)
allVecs.add(this.get(i));
for(int i = 0; i < Q.size(); i++)
allVecs.add(Q.get(i));
DistanceMetric dm = getDistanceMetric();
BaseCaseDT base;
if(!parallel)//easy serial case
base = (int r_indx, int q_indx) ->
{
double d = dm.dist(r_indx, N_r+q_indx, allVecs, wholeCache);
allPriorities.get(q_indx).add(new IndexDistPair(r_indx, d));
return d;
};
else//slightly more complicated parallel case
base = (int r_indx, int q_indx) ->
{
double d = dm.dist(r_indx, N_r + q_indx, allVecs, wholeCache);
BoundedSortedList target = allPriorities.get(q_indx);
synchronized (target)
{
target.add(new IndexDistPair(r_indx, d));
}
return d;
};
ScoreDTLazy score = (IndexNode ref, IndexNode query, double origScore) ->
{
if(origScore < 0)
return ref.minNodeDistance(query);
double bound_final = computeKnnBound(query, numNeighbors, allPriorities, query_B_cache);
final double d_min_b = origScore;
if(Double.isFinite(bound_final))
{
query_B_cache.put(query, bound_final);
if(d_min_b > bound_final)//YAY we can prune!
return Double.NaN;
}
//default case, don't prune
return d_min_b;
};
traverse(Q, base, score, true, parallel);
neighbors.clear();
distances.clear();
for(int i = 0; i < Q.size(); i++)
{
IntList n = new IntList(numNeighbors);
DoubleList d = new DoubleList(numNeighbors);
BoundedSortedList knn = allPriorities.get(i);
for(int j = 0; j < knn.size(); j++)
{
IndexDistPair ip = knn.get(j);
n.add(ip.getIndex());
d.add(ip.getDist());
}
neighbors.add(n);
distances.add(d);
}
}
default double computeKnnBound(IndexNode query, int numNeighbors, List> allPriorities, Map query_B_cache)
{
double bound_1 = Double.NEGATIVE_INFINITY;
for(int p = 0; p < query.numPoints(); p++)
{
BoundedSortedList D_p = allPriorities.get(query.getPoint(p));
if(D_p.size() == numNeighbors)//has enough neighbors to return a meaningful boun
bound_1 = max(bound_1, D_p.last().dist);
else//can't bound
{
bound_1 = Double.POSITIVE_INFINITY;
break;
}
}
if(Double.isInfinite(bound_1))//cant bound
bound_1 = Double.POSITIVE_INFINITY;
else//can bound, make it correct
for(int c = 0; c < query.numChildren(); c++)
{
double B_nc = query_B_cache.getOrDefault(query.getChild(c), Double.POSITIVE_INFINITY);
// if(Double.isInfinite(B_nc))//tighten by recursive search
// B_nc = computeKnnBound(query.getChild(c), numNeighbors, allPriorities, query_B_cache);
bound_1 = max(bound_1, B_nc);
}
///compute bound 2i. First set to infinity, and find min portion
double bound_2i = Double.POSITIVE_INFINITY;
for(int i = 0; i < query.numPoints(); i++)
{
int qi_indx = query.getPoint(i);
if(allPriorities.get(qi_indx).size() >= numNeighbors)
bound_2i = min(bound_2i, allPriorities.get(qi_indx).last().dist);
}
//then add the remaining 2 terms, which are constant for a given Node Q. If no valid points, bound remains infinite
bound_2i += query.furthestPointDistance() + query.furthestDescendantDistance();
//Compute 3rd bound
double lambda_q = query.furthestDescendantDistance();
double bound_3 = Double.POSITIVE_INFINITY;
for(int c = 0; c < query.numChildren(); c++)
{
IndexNode n_c = query.getChild(c);
double B_nc = query_B_cache.getOrDefault(n_c, Double.POSITIVE_INFINITY);
// if(Double.isInfinite(B_nc))//tighten by recursive search
// B_nc = computeKnnBound(n_c, numNeighbors, allPriorities, query_B_cache);
bound_3 = min(bound_3, B_nc + 2*(lambda_q-n_c.furthestDescendantDistance()));
}
IndexNode q_parrent = query.getParrent();
double bound_4 = q_parrent == null ? Double.POSITIVE_INFINITY : query_B_cache.getOrDefault(q_parrent, Double.POSITIVE_INFINITY);
final double bound_final = min(min(bound_1, bound_2i), min(bound_3, bound_4));
//update cache with min value
query_B_cache.compute(query, (IndexNode t, Double u) ->
{
if(u == null)
u = Double.POSITIVE_INFINITY;
return Math.min(u, bound_final);
});
// if(Double.isFinite(bound_3))
// System.out.println(bound_3);
return bound_final;
}
@Override
default public void search(VectorCollection VC, double r_min, double r_max, List> neighbors, List> distances, boolean parallel )
{
if(!(VC instanceof DualTree))
{
VectorCollection.super.search(VC, r_min, r_max, neighbors, distances, parallel);
return;
}
DualTree Q = (DualTree) VC;
neighbors.clear();
distances.clear();
for(int i = 0; i < Q.size(); i++)
{
if(parallel)
{
neighbors.add(Collections.synchronizedList(new IntList()));
distances.add(Collections.synchronizedList(new DoubleList()));
}
else
{
neighbors.add(new IntList());
distances.add(new DoubleList());
}
}
///For simplicity and fast calculations, lets combine acceleration caches into one view
final List this_cache = this.getAccelerationCache();
final List other_cache = Q.getAccelerationCache();
final int N_r = this.size();
final List wholeCache = this_cache == null ? null : ListUtils.mergedView(this_cache, other_cache);
final List allVecs = new ArrayList<>(N_r+Q.size());
for(int i = 0; i < N_r; i++)
allVecs.add(this.get(i));
for(int i = 0; i < Q.size(); i++)
allVecs.add(Q.get(i));
DistanceMetric dm = getDistanceMetric();
BaseCaseDT base = (int r_indx, int q_indx) ->
{
double d = dm.dist(r_indx, N_r+q_indx, allVecs, wholeCache);
if(r_min <= d && d <= r_max)
{
neighbors.get(q_indx).add(r_indx);
distances.get(q_indx).add(d);
}
return d;
};
ScoreDT score = (IndexNode ref, IndexNode query) ->
{
double[] minMax = ref.minMaxDistance(query);
double d_min = minMax[0];
double d_max = minMax[1];
if(d_min > r_max || d_max < r_min)//If min dist is greater than max-range, or max distance is greater than min-range, we can prune
return Double.NaN;
if(r_min < d_min && d_max < r_max)//Bound says ALL DECENDENTS BELONG, so lets do that!
{
IntList r_dec = new IntList();
for(Iterator iter = ref.DescendantIterator(); iter.hasNext(); )
r_dec.add(iter.next());
IntList q_dec = new IntList();
for(Iterator iter = query.DescendantIterator(); iter.hasNext(); )
q_dec.add(iter.next());
for(int i : r_dec)
for(int j : q_dec)
{
double d = dm.dist(i, N_r+j, allVecs, wholeCache);
neighbors.get(j).add(i);
distances.get(j).add(d);
}
//Return NaN so that search stops, we added everyone!
return Double.NaN;
}
return d_min;
};
//Range search dosn't benefit from improved search order. So use basic one and avoid extra overhead
traverse(Q, base, score, false, parallel);
//Now lets sort the returned lists
for(int i = 0; i < neighbors.size(); i++)
{
IndexTable it = new IndexTable(distances.get(i));
it.apply(distances.get(i));
it.apply(neighbors.get(i));
}
}
default void traverse(DualTree Q, BaseCaseDT base, ScoreDT score, boolean improvedTraverse, boolean parallel)
{
IndexNode R_root = this.getRoot(), Q_root = Q.getRoot();
if(!this.getRoot().allPointsInLeaves())//warp the roots so that we can use the same traversal for all implementations
{
R_root = new SelfAsChildNode<>(this.getRoot());
Q_root = new SelfAsChildNode<>(Q.getRoot());
}
if(parallel)
ForkJoinPool.commonPool().invoke(new DualTreeTraversalAction(R_root, Q_root, base, score, improvedTraverse));
else
dual_depth_first(R_root, Q_root, base, score, improvedTraverse);
}
/**
* This class is used as a helper class to deal with Dual Trees which may
* contain points in branching nodes. The dual tree traversal assumes all
* points belong in leaf nodes. This fixes that by wraping an IndexNode to
* behave as if all points owned within a branch really belong to a special
* extra "self" child.
*
* @param
*/
class SelfAsChildNode> implements IndexNode>
{
public boolean asLeaf;
N wrapping;
public SelfAsChildNode(N wrapping)
{
this.wrapping = wrapping;
asLeaf = !wrapping.hasChildren();
}
public SelfAsChildNode(boolean asLeaf, N wrapping)
{
this.asLeaf = asLeaf;
this.wrapping = wrapping;
}
@Override
public double furthestPointDistance()
{
if(!asLeaf)//Not acting as a leaf, so you don't have children!
return 0;
//else, return the answer
return wrapping.furthestPointDistance();
}
@Override
public double furthestDescendantDistance()
{
if(asLeaf)
return wrapping.furthestPointDistance();
else
return wrapping.furthestDescendantDistance();
}
@Override
public int numChildren()
{
if(asLeaf)
return 0;
else
return wrapping.numChildren() + 1;//+1 for self child
}
@Override
public IndexNode getChild(int indx)
{
if(indx == wrapping.numChildren())
return new SelfAsChildNode(true, wrapping);
//else, return base children
return new SelfAsChildNode(wrapping.getChild(indx));
}
@Override
public Vec getVec(int indx)
{
return wrapping.getVec(indx);
}
@Override
public int numPoints()
{
if(asLeaf)
return wrapping.numPoints();
else
return 0;
}
@Override
public int getPoint(int indx)
{
if(asLeaf)
return wrapping.getPoint(indx);
else//we can't have children if we aren't a leaf node!
throw new IndexOutOfBoundsException("Leaf node does not have any children");
}
@Override
public SelfAsChildNode getParrent()
{
if(asLeaf)
if(wrapping.hasChildren())//we are a branch node and acting as a leaf, so parrent its our non-leaf self
return new SelfAsChildNode<>(false, wrapping);
//we are true leaf node, parrent is just parrent
// OR
// we are not a leaf node, parrent is again just parrent
N parrent = wrapping.getParrent();
if(parrent == null)
return null;
return new SelfAsChildNode<>(false, parrent);
}
@Override
public double minNodeDistance(SelfAsChildNode other)
{
return wrapping.minNodeDistance(other.wrapping);
}
@Override
public double maxNodeDistance(SelfAsChildNode other)
{
return wrapping.maxNodeDistance(other.wrapping);
}
@Override
public double minNodeDistance(int other)
{
return wrapping.minNodeDistance(other);
}
@Override
public boolean equals(Object obj)
{
if(obj instanceof SelfAsChildNode)
{
SelfAsChildNode other = (SelfAsChildNode) obj;
if(this.asLeaf == other.asLeaf)
return this.wrapping.equals(other.wrapping);
}
return false;
}
@Override
public int hashCode()
{
int hash = 5;
hash = 71 * hash + (this.asLeaf ? 1 : 0);
if(this.wrapping == null)
System.out.println();
hash = 71 * hash + this.wrapping.hashCode();
return hash;
}
@Override
public double[] minMaxDistance(SelfAsChildNode other)
{
return wrapping.minMaxDistance(other.wrapping);
}
}
static final double COMP_SCORE = -1;
public static void dual_depth_first(IndexNode n_r, IndexNode n_q, BaseCaseDT base, ScoreDT score, boolean improvedSearch)
{
//Algo 10 in Thesis
//3: {Perform base cases for points in node combination.}
for(int i = 0; i < n_r.numPoints(); i++)
for(int j = 0; j < n_q.numPoints(); j++)
base.base_case(n_r.getPoint(i), n_q.getPoint(j));
//7: {Assemble list of combinations to recurse into.}
//8: q←empty priority queue
PriorityQueue q = new PriorityQueue<>();
//9: if Nq andNr both have children then
if(n_q.hasChildren() && n_r.hasChildren())
{
//the Algorithm 10 version. Simpler but not as efficent
if(!improvedSearch)
{
for(int i = 0; i < n_r.numChildren(); i++)
for(int j = 0; j < n_q.numChildren(); j++)
{
IndexNode n_r_i = n_r.getChild(i);
IndexNode n_q_j = n_q.getChild(j);
double s = score.score(n_r_i, n_q_j, COMP_SCORE);
if(!Double.isNaN(s))
q.offer(new IndexTuple(n_r_i, n_q_j, s));
}
}
else //Below is the Algo 13 version.
{
for(int c = 0; c < n_q.numChildren(); c++)
{
IndexNode n_q_c = n_q.getChild(c);
List q_qc =new ArrayList<>();
boolean all_scores_same = true;
for(int i = 0; i < n_r.numChildren(); i++)
{
IndexNode n_r_i = n_r.getChild(i);
double s = score.score(n_r_i, n_q_c, COMP_SCORE);
//check if all scores have the same value
if(i > 0 && abs(q_qc.get(i-1).priority-s) < 1e-13)
all_scores_same = false;
q_qc.add(new IndexTuple(n_r_i, n_q_c, s));
}
if(all_scores_same)
{
double s = score.score(n_r, n_q_c, COMP_SCORE);
q.offer(new IndexTuple(n_r, n_q_c, s));
}
else
q.addAll(q_qc);
}
}
}
else if(n_q.hasChildren()) //implicitly n_r has not children if this check passes
{
for(int j = 0; j < n_q.numChildren(); j++)
{
IndexNode n_q_j = n_q.getChild(j);
double s = score.score(n_r, n_q_j, COMP_SCORE);
if (!Double.isNaN(s))
q.offer(new IndexTuple(n_r, n_q_j, s));
}
}
else if(n_r.hasChildren())// implicitly n_q has no children if this check passes
{
for (int i = 0; i < n_r.numChildren(); i++)
{
IndexNode n_r_i = n_r.getChild(i);
double s = score.score(n_r_i, n_q, COMP_SCORE);
if (!Double.isNaN(s))
q.offer(new IndexTuple(n_r_i, n_q, s));
}
}
//22: {Recurse into combinations with highest priority first.
while(!q.isEmpty())
{
IndexTuple toProccess = q.poll();
if(score instanceof ScoreDTLazy)//re-compute the score before we just go in
{
double s = score.score(toProccess.a, toProccess.b, toProccess.priority);
if(Double.isNaN(s))//We might have a pruning op now
continue;//Good job!
}
dual_depth_first(toProccess.a, toProccess.b, base, score, improvedSearch);
}
}
class DualTreeTraversalAction extends RecursiveAction implements Comparable
{
IndexNode n_r;
IndexNode n_q;
BaseCaseDT base;
ScoreDT score;
boolean improvedSearch;
double priority;
public DualTreeTraversalAction(IndexNode n_r, IndexNode n_q, BaseCaseDT base, ScoreDT score, boolean improvedSearch)
{
this(n_r, n_q, base, score, improvedSearch, 0.0);
}
public DualTreeTraversalAction(IndexNode n_r, IndexNode n_q, BaseCaseDT base, ScoreDT score, boolean improvedSearch, double priority)
{
this.n_r = n_r;
this.n_q = n_q;
this.base = base;
this.score = score;
this.improvedSearch = improvedSearch;
this.priority = priority;
}
@Override
protected void compute()
{
/*
* B/c of fork-join framework, we can't do the ScoreDTLazy
* check before placing them into the execution que. So we will do
* them at the root no upon ourselves. We can do that b/c priority
* is the score for the pair of IndexNodes we are about to process!
*/
if(score instanceof ScoreDTLazy)//re-compute the score before we do work
{
double s = score.score(n_r, n_q, priority);
if(Double.isNaN(s))//We might have a pruning op now
return;//Good job! No more work to do
}
//Algo 10 in Thesis
//3: {Perform base cases for points in node combination.}
for(int i = 0; i < n_r.numPoints(); i++)
for(int j = 0; j < n_q.numPoints(); j++)
base.base_case(n_r.getPoint(i), n_q.getPoint(j));
//7: {Assemble list of combinations to recurse into.}
//8: q←empty priority queue
PriorityQueue q = new PriorityQueue<>();
//9: if Nq andNr both have children then
if(n_q.hasChildren() && n_r.hasChildren())
{
//the Algorithm 10 version. Simpler but not as efficent
if(!improvedSearch)
{
for(int i = 0; i < n_r.numChildren(); i++)
for(int j = 0; j < n_q.numChildren(); j++)
{
IndexNode n_r_i = n_r.getChild(i);
IndexNode n_q_j = n_q.getChild(j);
double s = score.score(n_r_i, n_q_j, COMP_SCORE);
if(!Double.isNaN(s))
q.offer(new DualTreeTraversalAction(n_r_i, n_q_j, base, score, improvedSearch, s));
}
}
else //Below is the Algo 13 version.
{
for(int c = 0; c < n_q.numChildren(); c++)
{
IndexNode n_q_c = n_q.getChild(c);
List q_qc =new ArrayList<>();
boolean all_scores_same = true;
for(int i = 0; i < n_r.numChildren(); i++)
{
IndexNode n_r_i = n_r.getChild(i);
double s = score.score(n_r_i, n_q_c, COMP_SCORE);
//check if all scores have the same value
if(i > 0 && abs(q_qc.get(i-1).priority-s) < 1e-13)
all_scores_same = false;
q_qc.add(new DualTreeTraversalAction(n_r_i, n_q_c, base, score, improvedSearch, s));
}
if(all_scores_same)
{
double s = score.score(n_r, n_q_c, COMP_SCORE);
q.offer(new DualTreeTraversalAction(n_r, n_q_c, base, score, improvedSearch, s));
}
else
q.addAll(q_qc);
}
}
}
else if(n_q.hasChildren()) //implicitly n_r has not children if this check passes
{
for(int j = 0; j < n_q.numChildren(); j++)
{
IndexNode n_q_j = n_q.getChild(j);
double s = score.score(n_r, n_q_j, COMP_SCORE);
if (!Double.isNaN(s))
q.offer(new DualTreeTraversalAction(n_r, n_q_j, base, score, improvedSearch, s));
}
}
else if(n_r.hasChildren())// implicitly n_q has no children if this check passes
{
for (int i = 0; i < n_r.numChildren(); i++)
{
IndexNode n_r_i = n_r.getChild(i);
double s = score.score(n_r_i, n_q, COMP_SCORE);
if (!Double.isNaN(s))
q.offer(new DualTreeTraversalAction(n_r_i, n_q, base, score, improvedSearch, s));
}
}
//22: {Recurse into combinations with highest priority first.
invokeAll(q);
}
@Override
public int compareTo(DualTreeTraversalAction o)
{
return Double.compare(this.priority, o.priority);
}
}
}
Ads help maintain this website.