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

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

java.lang.Object

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

Type Parameters:

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

D - the type of Distance used 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, MRadSplit

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

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

Field Summary

Fields

Modifier and Type	Field and Description
(package private) Assignments<D,E>	assignments Encapsulates the two promotion objects and their assignments.

Constructor Summary

Constructors

Constructor and Description
MTreeSplit()

Method Summary

Methods

Modifier and Type	Method and Description
private D	assignNN(Set<E> assigned1, Set<E> assigned2, List<DistanceEntry<D,E>> list, D currentCR, boolean isLeaf) 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<D,E>	balancedPartition(N node, DBID routingObject1, DBID routingObject2, DistanceQuery<O,D> distanceFunction) Creates a balanced partition of the entries of the specified node.
Assignments<D,E>	getAssignments() Returns the assignments of this split.

Methods inherited from class java.lang.Object

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

Field Detail

assignments

Assignments<D extends Distance<D>,E extends MTreeEntry<D>> assignments

Encapsulates the two promotion objects and their assignments.

Constructor Detail

MTreeSplit

public MTreeSplit()

Method Detail

balancedPartition

Assignments<D,E> balancedPartition(N node,
                                 DBID routingObject1,
                                 DBID routingObject2,
                                 DistanceQuery<O,D> distanceFunction)

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

Parameters:

node - the node to be split

routingObject1 - the id of the first routing object

routingObject2 - the id of the second routing object

distanceFunction - the distance function to compute the distances

Returns:

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

assignNN

private D assignNN(Set<E> assigned1,
         Set<E> assigned2,
         List<DistanceEntry<D,E>> list,
         D currentCR,
         boolean isLeaf)

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

Parameters:

assigned1 - the first assignment

assigned2 - the second assignment

list - the list, the first object should be assigned

currentCR - the current covering radius

isLeaf - true, if the node of the entries to be assigned is a leaf, false otherwise

Returns:

the new covering radius

getAssignments

public Assignments<D,E> getAssignments()

Returns the assignments of this split.

Returns:

the assignments of this split