Ignore:
Timestamp:
04/12/17 12:15:37 (2 years ago)
Author:
gkronber
Message:

#2700: made some changes / bug-fixes while reviewing

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/VantagePointTree.cs

    r14787 r14855  
    8484    public void Search(T target, int k, out IList<T> results, out IList<double> distances) {
    8585      var heap = new PriorityQueue<double, IndexedItem<double>>(double.MaxValue, double.MinValue, k);
    86       Search(root, target, k, heap, double.MaxValue);
     86      double tau = double.MaxValue;
     87      Search(root, target, k, heap, ref tau);
    8788      var res = new List<T>();
    8889      var dist = new List<double>();
    8990      while (heap.Size > 0) {
    90         res.Add(items[heap.PeekMinValue().Index]);
     91        res.Add(items[heap.PeekMinValue().Index]);          // actually max distance
    9192        dist.Add(heap.PeekMinValue().Value);
    9293        heap.RemoveMin();
    9394      }
    94       res.Reverse();
     95      res.Reverse(); 
    9596      dist.Reverse();
    9697      results = res;
     
    9899    }
    99100
    100     private void Search(Node node, T target, int k, PriorityQueue<double, IndexedItem<double>> heap, double tau = double.MaxValue) {
     101    private void Search(Node node, T target, int k, PriorityQueue<double, IndexedItem<double>> heap, ref double tau) {
    101102      if (node == null) return;
    102103      var dist = distance.Get(items[node.index], target);
    103104      if (dist < tau) {
    104         if (heap.Size == k) heap.RemoveMin();
    105         heap.Insert(-dist, new IndexedItem<double>(node.index, dist));//TODO check if minheap or maxheap should be used here
     105        if (heap.Size == k) heap.RemoveMin();   // remove furthest node from result list (if we already have k results)
     106        heap.Insert(-dist, new IndexedItem<double>(node.index, dist));     
    106107        if (heap.Size == k) tau = heap.PeekMinValue().Value;
    107108      }
     
    109110
    110111      if (dist < node.threshold) {
    111         if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau);   // if there can still be neighbors inside the ball, recursively search left child first
    112         if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau);  // if there can still be neighbors outside the ball, recursively search right child
     112        if (dist - tau <= node.threshold) Search(node.left, target, k, heap, ref tau);   // if there can still be neighbors inside the ball, recursively search left child first
     113        if (dist + tau >= node.threshold) Search(node.right, target, k, heap, ref tau);  // if there can still be neighbors outside the ball, recursively search right child
    113114      } else {
    114         if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau);  // if there can still be neighbors outside the ball, recursively search right child first
    115         if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau);   // if there can still be neighbors inside the ball, recursively search left child
     115        if (dist + tau >= node.threshold) Search(node.right, target, k, heap, ref tau);  // if there can still be neighbors outside the ball, recursively search right child first
     116        if (dist - tau <= node.threshold) Search(node.left, target, k, heap, ref tau);   // if there can still be neighbors inside the ball, recursively search left child
    116117      }
    117118    }
     
    124125      var node = new Node { index = lower };
    125126      var r = new MersenneTwister(); //outer behaviour does not change with the random seed => no need to take the IRandom from the algorithm
    126       if (upper - lower <= 1) return node; // if we did not arrive at leaf yet
     127      if (upper - lower <= 1) return node;
    127128
     129      // if we did not arrive at leaf yet
    128130      // Choose an arbitrary point and move it to the start
    129       var i = (int)(r.NextDouble() / 1 * (upper - lower - 1)) + lower;
     131      var i = (int)(r.NextDouble() * (upper - lower - 1)) + lower;
    130132      items.Swap(lower, i);
    131133
Note: See TracChangeset for help on using the changeset viewer.