Documentation of 'jsat.linear.vectorcollection.BallTree' Java class
BallTree
Skip navigation links
jsat.linear.vectorcollection

Class BallTree<V extends Vec>

  • Type Parameters:
    V -
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, DualTree<V>, IncrementalCollection<V>, VectorCollection<V>

    public class BallTree<V extends Vec>
extends java.lang.Object
implements IncrementalCollection<V>, DualTree<V>
    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 construction of the hierarchy is made, or how 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 BallTree.ConstructionMethod.TOP_DOWN_FARTHEST and BallTree.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
    See Also:
    Serialized Form

    • Method Detail

      • setLeafSize

        public void setLeafSize(int leaf_size)
        Sets the number of points stored within a leaf node of the index. Larger values avoid search overhead, but reduce opportunities for pruning.
        Parameters:
        leaf_size - the size of a leaf node. Must be at least 2

      • getLeafSize

        public int getLeafSize()
        Returns:
        the number of points to store within a leaf node

      • getMaxDepth

        public int getMaxDepth()
        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.
        Returns:
        the maximum current depth of this Ball Tree

      • build

        public void build(boolean parallel,
                  java.util.List<V> collection,
                  DistanceMetric dm)
        Description copied from interface: VectorCollection
        Builds this metric index from the given collection of points using the given distance metric.
        Specified by:
        build in interface VectorCollection<V extends Vec>
        Parameters:
        parallel - true if the index should be built in parallel, or false if it should be done in a single thread.
        collection - the list of vectors to put into the index
        dm - the distance metric to build the index using.

      • insert

        public void insert(V x)
        Description copied from interface: IncrementalCollection
        Incrementally adds the given datapoint into the collection
        Specified by:
        insert in interface IncrementalCollection<V extends Vec>
        Parameters:
        x - the vector to add to the collection

      • search

        public void search(Vec query,
                   double range,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)
        Description copied from interface: VectorCollection
        Performs a range search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.
        Specified by:
        search in interface VectorCollection<V extends Vec>
        Parameters:
        query - the point to search for the neighbors within a given radius.
        range - the radius to search for all the neighbors with a distance ≤ range.
        neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.
        distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

      • search

        public void search(Vec query,
                   int numNeighbors,
                   java.util.List<java.lang.Integer> neighbors,
                   java.util.List<java.lang.Double> distances)
        Description copied from interface: VectorCollection
        Performs k-Nearest Neighbor search of the current collection. The index and distance of each found neighbor will be placed into the given Lists.
        Specified by:
        search in interface DualTree<V extends Vec>
        Specified by:
        search in interface VectorCollection<V extends Vec>
        Parameters:
        query - the point to search for the k-nearest neighbors of
        numNeighbors - the number of neighbors k to search for.
        neighbors - the list to store the index of the neighbors in. Will be sorted by distance to the query, and paired with the values in distances.
        distances - the list to store the distance of the neighbors to the query in. Will be sorted, and paired with the values in neighbors.

      • get

        public V get(int indx)
        Description copied from interface: VectorCollection
        Accesses a vector from this collection via index.
        Specified by:
        get in interface VectorCollection<V extends Vec>
        Parameters:
        indx - the index in [0, VectorCollection.size()) of the vector to access
        Returns:
        the vector from the collection

      • size

        public int size()
        Description copied from interface: VectorCollection
        Returns the number of vectors stored in the collection
        Specified by:
        size in interface VectorCollection<V extends Vec>
        Returns:
        the size of the collection
Skip navigation links

DataMelt 3.0 © DataMelt by jWork.ORG

You see the box below because you did not login.