jsat.linear.vectorcollection

Class VPTreeMV<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.VPTree<V>

jsat.linear.vectorcollection.VPTreeMV<V>

All Implemented Interfaces:

Serializable, Cloneable, IncrementalCollection<V>, VectorCollection<V>

public class VPTreeMV<V extends Vec>
extends VPTree<V>

The VPTreeMV is an extension of the VPTree, the MV meaning "of Minimum Variance". This extension alters the splitting method of nodes, giving up the O(log n) bound on query time. This is done to reduce the variance in the distance to the parent node of each split, which can result in lopsided distributions of values for each split. At the same time, this lopsidedness may better reflect the locality of points in the data set. This can result in a decrease in query time for some data sets, with minimal impact on construction time.

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	VPTreeMV.VPTreeMVFactory<V extends Vec>

Nested classes/interfaces inherited from class jsat.linear.vectorcollection.VPTree

VPTree.VPSelection, VPTree.VPTreeFactory<V extends Vec>

Constructor Summary

Constructors

Constructor and Description
VPTreeMV(DistanceMetric dm)
VPTreeMV(List<V> list, DistanceMetric dm)
VPTreeMV(List<V> list, DistanceMetric dm, ExecutorService threadpool)
VPTreeMV(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection)
VPTreeMV(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, Random rand, int sampleSize, int searchIterations)
VPTreeMV(List<V> list, DistanceMetric dm, VPTree.VPSelection vpSelection, Random rand, int sampleSize, int searchIterations, ExecutorService threadpool)

Method Summary

Modifier and Type	Method and Description
protected int	splitListIndex(List<Pair<Double,Integer>> S) Determines which index to use as the splitting index for the VP radius

Methods inherited from class jsat.linear.vectorcollection.VPTree

clone, getMaxLeafSize, insert, search, search, setMaxLeafSize, size

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

VPTreeMV

public VPTreeMV(List<V> list,
                DistanceMetric dm,
                VPTree.VPSelection vpSelection,
                Random rand,
                int sampleSize,
                int searchIterations,
                ExecutorService threadpool)

VPTreeMV

public VPTreeMV(List<V> list,
                DistanceMetric dm,
                VPTree.VPSelection vpSelection,
                Random rand,
                int sampleSize,
                int searchIterations)

VPTreeMV

public VPTreeMV(List<V> list,
                DistanceMetric dm,
                VPTree.VPSelection vpSelection)

VPTreeMV

public VPTreeMV(List<V> list,
                DistanceMetric dm)

VPTreeMV

public VPTreeMV(List<V> list,
                DistanceMetric dm,
                ExecutorService threadpool)

VPTreeMV

public VPTreeMV(DistanceMetric dm)

Method Detail

splitListIndex

protected int splitListIndex(List<Pair<Double,Integer>> S)

Description copied from class: VPTree

Determines which index to use as the splitting index for the VP radius

Overrides:

splitListIndex in class VPTree<V extends Vec>

Parameters:

S - the non empty list of elements

Returns:

the index that should be used to split on [0, index] belonging to the left, and (index, S.size() ) belonging to the right.