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

Class HilOut.HilbertFeatures

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.outlier.distance.HilOut.HilbertFeatures

Enclosing class:

HilOut<O extends NumberVector>

class HilOut.HilbertFeatures
extends java.lang.Object

Class organizing the data points along a hilbert curve.

Author:

Jonathan von Brünken

Field Summary

Fields

Modifier and Type	Field and Description
(package private) double	diameter Data space diameter
(package private) double[]	min Data space minimums
private ObjectHeap<HilOut.HilFeature>	out "OUT"
(package private) HilOut.HilFeature[]	pf Hilbert representation ("point features")
(package private) Relation<O>	relation Relation indexed
(package private) double	shift Current curve shift
private java.util.Set<HilOut.HilFeature>	top Top candidates
private ObjectHeap<HilOut.HilFeature>	wlb "WLB"

Constructor Summary

Constructors

Constructor and Description
HilbertFeatures(Relation<O> relation, double[] min, double diameter) Constructor.

Method Summary

Modifier and Type	Method and Description
private double	boxRadius(int i, int a, int b) boxRadius function calculate the Boxradius
private double	fastUpperBound(int i) fastUpperBound function calculates an upper Bound as k*maxDist(pf[i], smallest neighborhood)
private double	getDimForObject(NumberVector obj, int dim) Get the (projected) position of the object in dimension dim.
private void	initialize(double shift) Hilbert function to fill pf with shifted Hilbert values.
private double	maxDistLevel(DBID id, int level) maxDist function calculate the maximal Distance from Vector p to the border of the corresponding r-region at the given level
private int	maxRegLevel(int ref, int q) Level of the maximum region containing ref but not q
private double	minDistLevel(DBID id, int level) minDist function calculate the minimal Distance from Vector p to the border of the corresponding r-region at the given level
private int	minRegLevel(int a, int b) minReg function calculate the minimal r-region level containing two points
private int	numberSharedLevels(long[] a, long[] b) Number of levels shared
private void	updateOUT(int i) updateOUT function inserts pf[i] in out.
private void	updateWLB(int i) updateWLB function inserts pf[i] in wlb.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

relation

Relation<O extends NumberVector> relation

Relation indexed

pf

HilOut.HilFeature[] pf

Hilbert representation ("point features")

min

double[] min

Data space minimums

diameter

double diameter

Data space diameter

shift

double shift

Current curve shift

top

private java.util.Set<HilOut.HilFeature> top

Top candidates

out

private ObjectHeap<HilOut.HilFeature> out

"OUT"

wlb

private ObjectHeap<HilOut.HilFeature> wlb

"WLB"

Constructor Detail

HilbertFeatures

public HilbertFeatures(Relation<O> relation,
                       double[] min,
                       double diameter)

Constructor.

Parameters:

relation - Relation to index

min - Minimums for data space

diameter - Diameter of data space

Method Detail

initialize

private void initialize(double shift)

Hilbert function to fill pf with shifted Hilbert values. Also calculates the number current Outlier candidates capital_n_star

Parameters:

shift - the new shift factor

updateOUT

private void updateOUT(int i)

updateOUT function inserts pf[i] in out.

Parameters:

i - position in pf of the feature to be inserted

updateWLB

private void updateWLB(int i)

updateWLB function inserts pf[i] in wlb.

Parameters:

i - position in pf of the feature to be inserted

fastUpperBound

private double fastUpperBound(int i)

fastUpperBound function calculates an upper Bound as k*maxDist(pf[i], smallest neighborhood)

Parameters:

i - position in pf of the feature for which the bound should be calculated

minDistLevel

private double minDistLevel(DBID id,
                            int level)

minDist function calculate the minimal Distance from Vector p to the border of the corresponding r-region at the given level

Parameters:

id - Object ID

level - Level of the corresponding r-region

maxDistLevel

private double maxDistLevel(DBID id,
                            int level)

maxDist function calculate the maximal Distance from Vector p to the border of the corresponding r-region at the given level

Parameters:

id - Object ID

level - Level of the corresponding r-region

numberSharedLevels

private int numberSharedLevels(long[] a,
                               long[] b)

Number of levels shared

Parameters:

a - First bitset

b - Second bitset

Returns:

Number of level shared

minRegLevel

private int minRegLevel(int a,
                        int b)

minReg function calculate the minimal r-region level containing two points

Parameters:

a - index of first point in pf

b - index of second point in pf

Returns:

Level of the r-region

maxRegLevel

private int maxRegLevel(int ref,
                        int q)

Level of the maximum region containing ref but not q

Parameters:

ref - Reference point

q - Query point

Returns:

Number of bits shared across all dimensions

boxRadius

private double boxRadius(int i,
                         int a,
                         int b)

boxRadius function calculate the Boxradius

Parameters:

i - index of first point

a - index of second point

b - index of third point

Returns:

box radius

getDimForObject

private double getDimForObject(NumberVector obj,
                               int dim)

Get the (projected) position of the object in dimension dim.

Parameters:

obj - Object

dim - Dimension

Returns:

Projected and shifted position