 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)
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.
• Constructor Detail

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,
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