E
- Entry typeN
- Node type@Priority(value=200) @Reference(authors="C. Traina Jr., A. J. M. Traina, B. Seeger, C. Faloutsos", title="Slim-Trees: High Performance Metric Trees Minimizing Overlap Between Nodes", booktitle="Int. Conf. Extending Database Technology (EDBT\'2000)", url="https://doi.org/10.1007/3-540-46439-5_4", bibkey="DBLP:conf/edbt/TrainaTSF00") public class MSTSplit<E extends MTreeEntry,N extends AbstractMTreeNode<?,N,E>> extends java.lang.Object implements MTreeSplit<E,N>
Unfortunately, the slim-tree paper does not detail how to choose the "most appropriate edge from the longest ones" (to find a more balanced split), so we try to longest 50%, and keep the choice which yields the most balanced split. This seems to work quite well.
Reference:
C. Traina Jr., A. J. M. Traina, B. Seeger, C. Faloutsos
Slim-Trees: High Performance Metric Trees Minimizing Overlap Between
Nodes
Int. Conf. Extending Database Technology (EDBT'2000)
Constructor and Description |
---|
MSTSplit() |
Modifier and Type | Method and Description |
---|---|
private static double |
coverRadius(double[][] matrix,
int[] idx,
int i)
Find the cover radius of a partition.
|
private static double |
edgelength(double[][] matrix,
int[] edges,
int i)
Length of edge i.
|
private static int |
follow(int i,
int[] partitions)
Union-find with simple path compression.
|
private static int[] |
mstPartition(double[][] matrix)
Partition the data using the minimu spanning tree.
|
private static void |
omitEdge(int[] edges,
int[] idx,
int[] sizes,
int omit)
Partition the data by omitting one edge.
|
Assignments<E> |
split(AbstractMTree<?,N,E,?> tree,
N node)
Returns the assignments of this split.
|
private static double |
thresholdLength(double[][] matrix,
int[] edges)
Choose the threshold length of edges to consider omittig.
|
public Assignments<E> split(AbstractMTree<?,N,E,?> tree, N node)
MTreeSplit
split
in interface MTreeSplit<E extends MTreeEntry,N extends AbstractMTreeNode<?,N,E>>
tree
- Tree to usenode
- Node to splitprivate static double coverRadius(double[][] matrix, int[] idx, int i)
matrix
- Distance matrixidx
- Partition keysi
- Candidate indexprivate static int[] mstPartition(double[][] matrix)
matrix
- private static double thresholdLength(double[][] matrix, int[] edges)
matrix
- Distance matrixedges
- Edgesprivate static double edgelength(double[][] matrix, int[] edges, int i)
matrix
- Distance matrixedges
- Edge listi
- Edge numberprivate static void omitEdge(int[] edges, int[] idx, int[] sizes, int omit)
edges
- Edges listidx
- Partition index storagesizes
- Partition sizesomit
- Edge number to omitprivate static int follow(int i, int[] partitions)
i
- Startpartitions
- Partitions arrayCopyright © 2019 ELKI Development Team. License information.