Class ALOCI.ALOCIQuadTree

  • Enclosing class:
    ALOCI<V extends NumberVector>

    static class ALOCI.ALOCIQuadTree
    extends java.lang.Object
    Simple quadtree for ALOCI. Not storing the actual objects, just the counts.

    Furthermore, the quadtree can be shifted by a specified vector, wrapping around min/max

    Author:
    Jonathan von Brünken, Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double[] min
      Tree parameters
      private int nmin
      Maximum fill for a page before splitting
      private Relation<? extends NumberVector> relation
      Relation indexed.
      (package private) ALOCI.Node root
      Tree root
      private double[] shift
      Tree parameters
      private double[] width
      Tree parameters
    • Constructor Summary

      Constructors 
      Constructor Description
      ALOCIQuadTree​(double[] min, double[] max, double[] shift, int nmin, Relation<? extends NumberVector> relation)
      Constructor.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void bulkLoad​(double[] lmin, double[] lmax, java.util.List<ALOCI.Node> children, ArrayModifiableDBIDs ids, int start, int end, int dim, int level, int code)
      Bulk load the tree
      ALOCI.Node findClosestNode​(NumberVector vec, int tlevel)
      Find the closest node (of depth tlevel or above, if there is no node at this depth) for the given vector.
      private double getShiftedDim​(NumberVector obj, int dim, int level)
      Shift and wrap a single dimension.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • shift

        private double[] shift
        Tree parameters
      • min

        private double[] min
        Tree parameters
      • width

        private double[] width
        Tree parameters
      • nmin

        private int nmin
        Maximum fill for a page before splitting
    • Constructor Detail

      • ALOCIQuadTree

        public ALOCIQuadTree​(double[] min,
                             double[] max,
                             double[] shift,
                             int nmin,
                             Relation<? extends NumberVector> relation)
        Constructor.
        Parameters:
        min - Minimum coordinates
        max - Maximum coordinates
        shift - Tree shift offset
        nmin - Maximum size for a page to split
        relation - Relation to index
    • Method Detail

      • bulkLoad

        private void bulkLoad​(double[] lmin,
                              double[] lmax,
                              java.util.List<ALOCI.Node> children,
                              ArrayModifiableDBIDs ids,
                              int start,
                              int end,
                              int dim,
                              int level,
                              int code)
        Bulk load the tree
        Parameters:
        lmin - Subtree minimum (unshifted, will be modified)
        lmax - Subtree maximum (unshifted, will be modified)
        children - List of children for current parent
        ids - IDs to process
        start - Start of ids subinterval
        end - End of ids subinterval
        dim - Current dimension
        level - Current tree level
        code - Bit code of node position
      • getShiftedDim

        private double getShiftedDim​(NumberVector obj,
                                     int dim,
                                     int level)
        Shift and wrap a single dimension.
        Parameters:
        obj - Object
        dim - Dimension
        level - Level (controls scaling/wrapping!)
        Returns:
        Shifted position
      • findClosestNode

        public ALOCI.Node findClosestNode​(NumberVector vec,
                                          int tlevel)
        Find the closest node (of depth tlevel or above, if there is no node at this depth) for the given vector.
        Parameters:
        vec - Query vector
        tlevel - Target level
        Returns:
        Node