de.lmu.ifi.dbs.elki.algorithm.outlier.lof

Class ALOCI.ALOCIQuadTree

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.ALOCI.ALOCIQuadTree

Enclosing class:

ALOCI<O 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 and 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 and Description
ALOCIQuadTree(double[] min, double[] max, double[] shift, int nmin, Relation<? extends NumberVector> relation) Constructor.

Method Summary

Modifier and Type	Method and 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

root

ALOCI.Node root

Tree root

relation

private Relation<? extends NumberVector> relation

Relation indexed.

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