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<?>,D extends NumberDistance<D,?>>

static class ALOCI.ALOCIQuadTree
extends 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

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

Method Summary

Methods

Modifier and Type	Method and Description
private void	bulkLoad(double[] lmin, double[] lmax, 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

ALOCI.ALOCIQuadTree

public ALOCI.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,
            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/wraping!)

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