Class KdTreeSearchBestBinFirst<P>

java.lang.Object
org.ddogleg.nn.alg.searches.KdTreeSearchBestBinFirst<P>
Direct Known Subclasses:
KdTreeSearch1Bbf, KdTreeSearchNBbf

public abstract class KdTreeSearchBestBinFirst<P>
extends Object

Approximate search for K-D Trees using the best-bin-first method [1] that supports multiple trees. A priority queue is created where nodes that are more likely to contain points close to the target are given higher priority. It is approximate since only predetermined number of nodes are considered.

Searches are initialized by searching each tree at least once down to a leaf. As these searches are performed, unexplored regions are added to the priority queue. Searching multiple trees is in response to [2], which proposes using a set of random trees to improve search performance and take better advantage of structure found in the data.

[1] Beis, Jeffrey S. and Lowe, David G, "Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces" CVPR 1997
[2] Silpa-Anan, C. and Hartley, R. "Optimised KD-trees for fast image descriptor matching" CVPR 2008

  • Field Details

    • maxNodesSearched

      protected int maxNodesSearched
    • N

      protected int N
    • bestDistanceSq

      protected double bestDistanceSq
    • numNodesSearched

      protected int numNodesSearched
  • Constructor Details

    • KdTreeSearchBestBinFirst

      protected KdTreeSearchBestBinFirst​(KdTreeDistance<P> distance, int maxNodesSearched)
      Configures the search
      Parameters:
      maxNodesSearched - Maximum number of nodes it will search. Used to limit CPU time.
  • Method Details

    • setTree

      public void setTree​(KdTree tree)
    • setTrees

      public void setTrees​(KdTree[] trees)
    • setMaxDistance

      public void setMaxDistance​(double maxDistance)
    • _findClosest

      public void _findClosest​(P target)
    • searchNode

      protected void searchNode​(P target, KdTree.Node n)
      Traverse a node down to a leaf. Unexplored branches are added to the priority queue.
    • addToQueue

      protected void addToQueue​(double closestDistanceSq, KdTree.Node node, P target)
      Adds a node to the priority queue.
      Parameters:
      closestDistanceSq - The closest distance that a point in the region could possibly be target
    • checkBestDistance

      protected abstract void checkBestDistance​(KdTree.Node node, P target)
      Checks to see if the current node's point is the closet point found so far
    • canImprove

      protected abstract boolean canImprove​(double distanceSq)
      Checks to see if it is possible for this distance to improve upon the current best
      Parameters:
      distanceSq - The distance being considered
      Returns:
      true if it can be better or false if not