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

Class SVPTree<V extends Vec>

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

    public class SVPTree<V extends Vec>
extends java.lang.Object
implements IncrementalCollection<V>, DualTree<V>
    Provides a simplified implementation of Vantage Point Trees, as described in "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces" by Peter N. Yianilos
    VPTrees are more expensive to create, requiring O(n log n) distance computations. However, they work well for high dimensional data sets, and provide O( log n ) query time for VectorCollection.search(jsat.linear.Vec, int)
    See Also:
    Serialized Form

    • Constructor Detail

      • SVPTree

        public SVPTree(java.util.List<V> list,
               DistanceMetric dm,
               boolean parallel)

      • SVPTree

        public SVPTree()

    • Method Detail

      • dist

        public double dist(int self_index,
                   int other_index,
                   DualTree<V> other)
        Specified by:
        dist in interface DualTree<V extends Vec>

      • build

        public void build(boolean parallel,
                  java.util.List<V> list,
                  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.
        list - the list of vectors to put into the index
        dm - the distance metric to build the index using.

      • 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

      • 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

      • 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.

      • getMaxLeafSize

        public int getMaxLeafSize()
        Returns the maximum leaf node size. Leaf nodes are used to reduce inefficiency of splitting small lists. If a sublist will fit into a leaf node, a leaf node will be created instead of splitting. This is the maximum number of points that may be used to construct a leaf node.
        Returns:
        the maximum leaf node size in the tree

      • setMaxLeafSize

        public void setMaxLeafSize(int maxLeafSize)
        Sets the maximum leaf node size. Leaf nodes are used to reduce inefficiency of splitting small lists. If a sublist will fit into a leaf node, a leaf node will be created instead of splitting. This is the maximum number of points that may be used to construct a leaf node.
        The minimum leaf size is 5 for implementation reasons. If a value less than 5 is given, 5 will be used isntead.
        Parameters:
        maxLeafSize - the new maximum leaf node size.
Skip navigation links

DataMelt 3.0 © DataMelt by jWork.ORG

You see the box below because you did not login.