Package elki.outlier.lof

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