Package elki.projection

Class 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 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 Description
      private QuadTree​(double[][] data, BarnesHutTSNE.QuadTree[] children, double[] mid, int weight, double squareSize)
      Constructor.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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

      • 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