de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split

Class MTreeSplit<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MTreeSplit<O,N,E>

Type Parameters:

O - the type of DatabaseObject to be stored in the M-Tree

N - the type of AbstractMTreeNode used in the M-Tree

E - the type of MetricalEntry used in the M-Tree

Direct Known Subclasses:

MLBDistSplit, MMRadSplit, MRadSplit, RandomSplit

public abstract class MTreeSplit<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry>
extends Object

Abstract super class for splitting a node in an M-Tree.

Since:

0.2

Author:

Elke Achtert

Constructor Summary

Constructors

Constructor and Description
MTreeSplit()

Method Summary

Methods

Modifier and Type	Method and Description
private int	assignBest(Assignments<E> assign, long[] assigned, N node, double[] dis, int[] idx, int pos, boolean second) Assigns the first object of the specified list to the first assignment that it is not yet assigned to the second assignment.
(package private) Assignments<E>	balancedPartition(AbstractMTree<O,N,E,?> tree, N node, DBID routingObject1, DBID routingObject2) Creates a balanced partition of the entries of the specified node.
(package private) Assignments<E>	balancedPartition(AbstractMTree<O,N,E,?> tree, N node, int routingEntNum1, int routingEntNum2, double[] distanceMatrix) Creates a balanced partition of the entries of the specified node.
protected double[]	computeDistanceMatrix(AbstractMTree<O,N,E,?> tree, N node) Compute the pairwise distances in the given node.
abstract Assignments<E>	split(AbstractMTree<O,N,E,?> tree, N node) Returns the assignments of this split.

Methods inherited from class java.lang.Object

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

Constructor Detail

MTreeSplit

public MTreeSplit()

Method Detail

computeDistanceMatrix

protected double[] computeDistanceMatrix(AbstractMTree<O,N,E,?> tree,
                             N node)

Compute the pairwise distances in the given node.

Parameters:

tree - Tree

node - Node

Returns:

Distance matrix

balancedPartition

Assignments<E> balancedPartition(AbstractMTree<O,N,E,?> tree,
                               N node,
                               DBID routingObject1,
                               DBID routingObject2)

Creates a balanced partition of the entries of the specified node.

Parameters:

tree - the tree to perform the split in

node - the node to be split

routingObject1 - the id of the first routing object

routingObject2 - the id of the second routing object

Returns:

an assignment that holds a balanced partition of the entries of the specified node

balancedPartition

Assignments<E> balancedPartition(AbstractMTree<O,N,E,?> tree,
                               N node,
                               int routingEntNum1,
                               int routingEntNum2,
                               double[] distanceMatrix)

Creates a balanced partition of the entries of the specified node.

Parameters:

tree - the tree to perform the split in

node - the node to be split

routingEntNum1 - the entry number of the first routing object

routingEntNum2 - the entry number of the second routing object

distanceMatrix - precomputed distance matrix to use

Returns:

an assignment that holds a balanced partition of the entries of the specified node

assignBest

private int assignBest(Assignments<E> assign,
             long[] assigned,
             N node,
             double[] dis,
             int[] idx,
             int pos,
             boolean second)

Assigns the first object of the specified list to the first assignment that it is not yet assigned to the second assignment.

Parameters:

assign - Output assignment

assigned - Bitset of assigned objects

dis - Distances

idx - Indexes

pos - Current position

second - Assign to second, not first, set.

Returns:

the new index

split

public abstract Assignments<E> split(AbstractMTree<O,N,E,?> tree,
                   N node)

Returns the assignments of this split.

Parameters:

tree - Tree to use

node - Node to split

Returns:

the assignments of this split