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

• java.lang.Object
• 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

All Methods
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

private QuadTree(double[][] data,
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:
• #### 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