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

Class MLBDistSplit<E extends MTreeEntry,N extends AbstractMTreeNode<?,N,E>>

java.lang.Object

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

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

Type Parameters:

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

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

All Implemented Interfaces:

MTreeSplit<E,N>

@Priority(value=200)
 @Reference(authors="P. Ciaccia, M. Patella, P. Zezula",
           title="M-tree: An Efficient Access Method for Similarity Search in Metric Spaces",
           booktitle="Proc. Int. Conf. Very Large Data Bases (VLDB\'97)",
           url="http://www.vldb.org/conf/1997/P426.PDF",
           bibkey="DBLP:conf/vldb/CiacciaPZ97")
 @Alias(value="de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.split.MLBDistSplit")
public class MLBDistSplit<E extends MTreeEntry,N extends AbstractMTreeNode<?,N,E>>
extends AbstractMTreeSplit<E,N>

Encapsulates the required methods for a split of a node in an M-Tree. The routing objects are chosen according to the MLBDIST strategy.

The benefit of this strategy is that it works with precomputed distances from the parent, while most other strategies would require O(n²) distance computations. So if construction time is critical, this is a good choice.

Reference:

P. Ciaccia, M. Patella, P. Zezula
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
Proc. Int. Conf. Very Large Data Bases (VLDB'97)

Since:

0.6.0

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MLBDistSplit.Parameterizer<E extends MTreeEntry,N extends AbstractMTreeNode<?,N,E>> Parameterization class.

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.AbstractMTreeSplit

distributor

Constructor Summary

Constructors

Constructor and Description
MLBDistSplit(DistributionStrategy distributor) Constructor.

Method Summary

Modifier and Type	Method and Description
Assignments<E>	split(AbstractMTree<?,N,E,?> tree, N node) Selects the second object of the specified node to be promoted and stored into the parent node and partitions the entries according to the M_LB_DIST strategy.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.AbstractMTreeSplit

computeDistanceMatrix

Methods inherited from class java.lang.Object

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

Constructor Detail

MLBDistSplit

public MLBDistSplit(DistributionStrategy distributor)

Constructor.

Parameters:

distributor - Distribution strategy

Method Detail

split

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

Selects the second object of the specified node to be promoted and stored into the parent node and partitions the entries according to the M_LB_DIST strategy.

This strategy considers all possible pairs of objects and chooses the pair of objects for which the distance is maximum.

Parameters:

tree - Tree to use

node - the node to be split

Returns:

the assignments of this split