summaryrefslogtreecommitdiff
path: root/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java')
-rw-r--r--src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java59
1 files changed, 30 insertions, 29 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java
index 167b5368..89b323a7 100644
--- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java
+++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MTreeSplit.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split;
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
- Copyright (C) 2013
+ Copyright (C) 2014
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
@@ -30,7 +30,6 @@ import java.util.List;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
-import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance;
import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree;
import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode;
import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry;
@@ -43,11 +42,10 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry;
* @apiviz.composedOf Assignments
*
* @param <O> the type of DatabaseObject to be stored in the M-Tree
- * @param <D> the type of Distance used in the M-Tree
* @param <N> the type of AbstractMTreeNode used in the M-Tree
* @param <E> the type of MetricalEntry used in the M-Tree
*/
-public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> {
+public abstract class MTreeSplit<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> {
/**
* Compute the pairwise distances in the given node.
*
@@ -55,18 +53,20 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
* @param node Node
* @return Distance matrix
*/
- protected double[] computeDistanceMatrix(AbstractMTree<O, D, N, E, ?> tree, N node) {
+ protected double[] computeDistanceMatrix(AbstractMTree<O, N, E, ?> tree, N node) {
final int n = node.getNumEntries();
double[] distancematrix = new double[n * n];
// Build distance matrix
- for (int i = 0; i < n; i++) {
+ for(int i = 0; i < n; i++) {
E ei = node.getEntry(i);
- for (int j = 0; j < n; j++) {
- if (i == j) {
+ for(int j = 0; j < n; j++) {
+ if(i == j) {
distancematrix[i * n + j] = 0.0;
- } else if (i < j) {
- distancematrix[i * n + j] = tree.distance(ei, node.getEntry(j)).doubleValue();
- } else { // i > j
+ }
+ else if(i < j) {
+ distancematrix[i * n + j] = tree.distance(ei, node.getEntry(j));
+ }
+ else { // i > j
distancematrix[i * n + j] = distancematrix[j * n + i];
}
}
@@ -84,7 +84,7 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
* @return an assignment that holds a balanced partition of the entries of the
* specified node
*/
- Assignments<E> balancedPartition(AbstractMTree<O, D, N, E, ?> tree, N node, DBID routingObject1, DBID routingObject2) {
+ Assignments<E> balancedPartition(AbstractMTree<O, N, E, ?> tree, N node, DBID routingObject1, DBID routingObject2) {
BitSet assigned = new BitSet(node.getNumEntries());
List<DistanceEntry<E>> assigned1 = new ArrayList<>(node.getCapacity());
List<DistanceEntry<E>> assigned2 = new ArrayList<>(node.getCapacity());
@@ -96,20 +96,20 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
List<DistanceEntry<E>> list2 = new ArrayList<>();
// determine the nearest neighbors
- for (int i = 0; i < node.getNumEntries(); i++) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
final E ent = node.getEntry(i);
DBID id = ent.getRoutingObjectID();
- if (DBIDUtil.equal(id, routingObject1)) {
+ if(DBIDUtil.equal(id, routingObject1)) {
assigned1.add(new DistanceEntry<>(ent, 0., i));
continue;
}
- if (DBIDUtil.equal(id, routingObject2)) {
+ if(DBIDUtil.equal(id, routingObject2)) {
assigned2.add(new DistanceEntry<>(ent, 0., i));
continue;
}
// determine the distance of o to o1 / o2
- double d1 = tree.distance(routingObject1, id).doubleValue();
- double d2 = tree.distance(routingObject2, id).doubleValue();
+ double d1 = tree.distance(routingObject1, id);
+ double d2 = tree.distance(routingObject2, id);
list1.add(new DistanceEntry<>(ent, d1, i));
list2.add(new DistanceEntry<>(ent, d2, i));
@@ -117,10 +117,10 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
Collections.sort(list1, Collections.reverseOrder());
Collections.sort(list2, Collections.reverseOrder());
- for (int i = 2; i < node.getNumEntries(); i++) {
+ for(int i = 2; i < node.getNumEntries(); i++) {
currentCR1 = assignNN(assigned, assigned1, list1, currentCR1, node.isLeaf());
i++;
- if (i < node.getNumEntries()) {
+ if(i < node.getNumEntries()) {
currentCR2 = assignNN(assigned, assigned2, list2, currentCR2, node.isLeaf());
}
}
@@ -138,7 +138,7 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
* @return an assignment that holds a balanced partition of the entries of the
* specified node
*/
- Assignments<E> balancedPartition(AbstractMTree<O, D, N, E, ?> tree, N node, int routingEntNum1, int routingEntNum2, double[] distanceMatrix) {
+ Assignments<E> balancedPartition(AbstractMTree<O, N, E, ?> tree, N node, int routingEntNum1, int routingEntNum2, double[] distanceMatrix) {
final int n = node.getNumEntries();
BitSet assigned = new BitSet(node.getNumEntries());
List<DistanceEntry<E>> assigned1 = new ArrayList<>(node.getCapacity());
@@ -152,14 +152,14 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
DBID routingObject1 = null, routingObject2 = null;
// determine the nearest neighbors
- for (int i = 0; i < node.getNumEntries(); i++) {
+ for(int i = 0; i < node.getNumEntries(); i++) {
final E ent = node.getEntry(i);
- if (i == routingEntNum1) {
+ if(i == routingEntNum1) {
routingObject1 = ent.getRoutingObjectID();
assigned1.add(new DistanceEntry<>(ent, 0., i));
continue;
}
- if (i == routingEntNum2) {
+ if(i == routingEntNum2) {
routingObject2 = ent.getRoutingObjectID();
assigned2.add(new DistanceEntry<>(ent, 0., i));
continue;
@@ -174,10 +174,10 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
Collections.sort(list1, Collections.reverseOrder());
Collections.sort(list2, Collections.reverseOrder());
- for (int i = 2; i < node.getNumEntries(); i++) {
+ for(int i = 2; i < node.getNumEntries(); i++) {
currentCR1 = assignNN(assigned, assigned1, list1, currentCR1, node.isLeaf());
i++;
- if (i < node.getNumEntries()) {
+ if(i < node.getNumEntries()) {
currentCR2 = assignNN(assigned, assigned2, list2, currentCR2, node.isLeaf());
}
}
@@ -199,15 +199,16 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
private double assignNN(BitSet assigned, List<DistanceEntry<E>> assigned1, List<DistanceEntry<E>> list, double currentCR, boolean isLeaf) {
// Remove last unassigned:
DistanceEntry<E> distEntry = list.remove(list.size() - 1);
- while (assigned.get(distEntry.getIndex())) {
+ while(assigned.get(distEntry.getIndex())) {
distEntry = list.remove(list.size() - 1);
}
assigned1.add(distEntry);
assigned.set(distEntry.getIndex());
- if (isLeaf) {
+ if(isLeaf) {
return Math.max(currentCR, distEntry.getDistance());
- } else {
+ }
+ else {
return Math.max(currentCR, distEntry.getDistance() + (distEntry.getEntry()).getCoveringRadius());
}
}
@@ -219,5 +220,5 @@ public abstract class MTreeSplit<O, D extends NumberDistance<D, ?>, N extends Ab
* @param node Node to split
* @return the assignments of this split
*/
- abstract public Assignments<E> split(AbstractMTree<O, D, N, E, ?> tree, N node);
+ abstract public Assignments<E> split(AbstractMTree<O, N, E, ?> tree, N node);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-01 16:59:00 +0000