de.lmu.ifi.dbs.elki.algorithm.projection

Class BarnesHutTSNE.QuadTree

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.projection.BarnesHutTSNE.QuadTree

Enclosing class:

BarnesHutTSNE<O>

protected static class BarnesHutTSNE.QuadTree
extends java.lang.Object

Quad Tree for use in a Barnes-Hut approximation.

This tree stores in every node the number of points contained, the center of mass, and the diagonal of the cell.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
double[]	center Center of mass (NOT center of bounding box)
BarnesHutTSNE.QuadTree[]	children Child nodes.
double[][]	points Points stored in this node.
double	squareSize Square size of this node, for Barnes-Hut approximation.
int	weight Total weight of this node.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	QuadTree(double[][] data, BarnesHutTSNE.QuadTree[] children, double[] mid, int weight, double squareSize) Constructor.

Method Summary

Modifier and Type	Method and Description
static BarnesHutTSNE.QuadTree	build(int dim, double[][] data) Construct the quad tree approximation.
private static BarnesHutTSNE.QuadTree	build(int dim, double[][] data, int begin, int end) Recursive build function.
private static double[]	computeCenterofMass(int dim, double[][] data, int begin, int end) Computer the center of mass.
private static double[]	computeExtend(int dim, double[][] data, int begin, int end) Compute the bounding box of a data set.
private static double	computeSquareSize(double[] minmax) Compute the square size of a bounding box.
private static void	splitRecursively(double[][] data, int begin, int end, int initdim, int dims, double[] minmax, java.util.ArrayList<double[]> singletons, java.util.ArrayList<BarnesHutTSNE.QuadTree> children) Build the quadtree by recursive splitting.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

center

public double[] center

Center of mass (NOT center of bounding box)

points

public double[][] points

Points stored in this node.

squareSize

public double squareSize

Square size of this node, for Barnes-Hut approximation.

weight

public int weight

Total weight of this node.

children

public BarnesHutTSNE.QuadTree[] children

Child nodes.

Constructor Detail

QuadTree

private QuadTree(double[][] data,
                 BarnesHutTSNE.QuadTree[] children,
                 double[] mid,
                 int weight,
                 double squareSize)

Constructor.

Parameters:

data - Data points

children - Child nodes

mid - Center of mass

weight - Node weight

squareSize - Square size of the node

Method Detail

build

public static BarnesHutTSNE.QuadTree build(int dim,
                                           double[][] data)

Construct the quad tree approximation.

Parameters:

dim - Dimensionality

data - Data set (will be modified!)

Returns:

Quad tree

build

private static BarnesHutTSNE.QuadTree build(int dim,
                                            double[][] data,
                                            int begin,
                                            int end)

Recursive build function.

Parameters:

dim - Dimensionality

data - Input data (WILL BE MODIFIED)

begin - Subset begin

end - Subset end

Returns:

Subtree

splitRecursively

private static void splitRecursively(double[][] data,
                                     int begin,
                                     int end,
                                     int initdim,
                                     int dims,
                                     double[] minmax,
                                     java.util.ArrayList<double[]> singletons,
                                     java.util.ArrayList<BarnesHutTSNE.QuadTree> children)

Build the quadtree by recursive splitting.

Parameters:

data - Input data

begin - Subset begin

end - Subset end

initdim - Current dimension

dims - Data dimensionality

minmax - Bounding box

singletons - Output for singletons

children - Output for child nodes

computeCenterofMass

private static double[] computeCenterofMass(int dim,
                                            double[][] data,
                                            int begin,
                                            int end)

Computer the center of mass.

Parameters:

dim - Dimensionality

data - Data set

begin - Begin of subset

end - End of subset

Returns:

Center of mass

computeExtend

private static double[] computeExtend(int dim,
                                      double[][] data,
                                      int begin,
                                      int end)

Compute the bounding box of a data set.

Parameters:

dim - Dimensionality

data - Data set

begin - Begin of subset

end - End of subset

Returns:

Bounding box

computeSquareSize

private static double computeSquareSize(double[] minmax)

Compute the square size of a bounding box.

Note that van der Maaten writes "diagonal", while his source code uses the maximum edge length. Barnes and Hut used the cell edge size of a square quad tree.

Parameters:

minmax - Bounding box

Returns:

squared cell size

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object