diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants')
74 files changed, 697 insertions, 1097 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java index 61ca9116..f1ef3b9b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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.DBIDRef; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.BreadthFirstEnumeration; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; import de.lmu.ifi.dbs.elki.index.tree.TreeIndexPathComponent; @@ -54,12 +53,11 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; * @apiviz.excludeSubtypes * * @param <O> the type of DatabaseObject to be stored in the metrical index - * @param <D> the type of Distance used in the metrical index * @param <N> the type of MetricalNode used in the metrical index * @param <E> the type of MetricalEntry used in the metrical index * @param <S> the type to store settings in. */ -public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, D, N, E>> extends MetricalIndexTree<O, D, N, E> { +public abstract class AbstractMTree<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, N, E>> extends MetricalIndexTree<O, N, E> { /** * Debugging flag: do extra integrity checks. */ @@ -87,20 +85,11 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends } @Override - public final DistanceFunction<? super O, D> getDistanceFunction() { + public final DistanceFunction<? super O> getDistanceFunction() { return settings.distanceFunction; } /** - * Get the distance factory. - * - * @return the distance factory used - */ - public final D getDistanceFactory() { - return settings.distanceFunction.getDistanceFactory(); - } - - /** * Returns a string representation of this M-Tree by performing a breadth * first enumeration on the tree and adding the string representation of the * visited nodes and their entries to the result. @@ -117,8 +106,8 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends N node = getRoot(); - while (!node.isLeaf()) { - if (node.getNumEntries() > 0) { + while(!node.isLeaf()) { + if(node.getNumEntries() > 0) { E entry = node.getEntry(0); node = getNode(entry); levels++; @@ -126,20 +115,22 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends } BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<>(this, getRootPath()); - while (enumeration.hasMoreElements()) { + while(enumeration.hasMoreElements()) { IndexTreePath<E> path = enumeration.nextElement(); E entry = path.getLastPathComponent().getEntry(); - if (entry.isLeafEntry()) { + if(entry.isLeafEntry()) { objects++; result.append("\n ").append(entry.toString()); - } else { + } + else { node = getNode(entry); result.append("\n\n").append(node).append(", numEntries = ").append(node.getNumEntries()); result.append("\n").append(entry.toString()); - if (node.isLeaf()) { + if(node.isLeaf()) { leafNodes++; - } else { + } + else { dirNodes++; } } @@ -165,27 +156,27 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends */ // todo: implement a bulk load for M-Tree and remove this method public void insert(E entry, boolean withPreInsert) { - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { getLogger().debugFine("insert " + entry.getRoutingObjectID() + "\n"); } - if (!initialized) { + if(!initialized) { initialize(entry); } // choose subtree for insertion IndexTreePath<E> subtree = settings.insertStrategy.choosePath(this, entry); - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { getLogger().debugFine("insertion-subtree " + subtree + "\n"); } // determine parent distance E parentEntry = subtree.getLastPathComponent().getEntry(); - double parentDistance = distance(parentEntry.getRoutingObjectID(), entry.getRoutingObjectID()).doubleValue(); + double parentDistance = distance(parentEntry.getRoutingObjectID(), entry.getRoutingObjectID()); entry.setParentDistance(parentDistance); // create leaf entry and do pre insert - if (withPreInsert) { + if(withPreInsert) { preInsert(entry); } @@ -198,8 +189,8 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends adjustTree(subtree); // test - if (EXTRA_INTEGRITY_CHECKS) { - if (withPreInsert) { + if(EXTRA_INTEGRITY_CHECKS) { + if(withPreInsert) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -211,10 +202,10 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * @param entries Entries to insert */ public void insertAll(List<E> entries) { - if (!initialized && entries.size() > 0) { + if(!initialized && entries.size() > 0) { initialize(entries.get(0)); } - for (E entry : entries) { + for(E entry : entries) { insert(entry, false); } } @@ -236,9 +227,9 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends protected final List<DoubleIntPair> getSortedEntries(N node, DBID q) { List<DoubleIntPair> result = new ArrayList<>(); - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); - double distance = distance(entry.getRoutingObjectID(), q).doubleValue(); + double distance = distance(entry.getRoutingObjectID(), q); double radius = entry.getCoveringRadius(); double minDist = (radius > distance) ? 0.0 : distance - radius; @@ -256,7 +247,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * @param id2 the second id * @return the distance between the two specified ids */ - public abstract D distance(DBIDRef id1, DBIDRef id2); + public abstract double distance(DBIDRef id1, DBIDRef id2); /** * Returns the distance between the routing object of two entries. @@ -265,7 +256,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * @param e2 Second entry * @return the distance between the two routing objects */ - public final D distance(E e1, E e2) { + public final double distance(E e1, E e2) { return distance(e1.getRoutingObjectID(), e2.getRoutingObjectID()); } @@ -286,7 +277,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * @param subtree the subtree to be adjusted */ private void adjustTree(IndexTreePath<E> subtree) { - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { getLogger().debugFine("Adjust tree " + subtree + "\n"); } @@ -295,7 +286,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends N node = getNode(subtree.getLastPathComponent().getEntry()); // overflow in node; split the node - if (hasOverflow(node)) { + if(hasOverflow(node)) { // do the split Assignments<E> assignments = settings.splitStrategy.split(this, node); final N newNode = node.isLeaf() ? createNewLeafNode() : createNewDirectoryNode(); @@ -303,12 +294,12 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends List<E> entries1 = new ArrayList<>(assignments.getFirstAssignments().size()); List<E> entries2 = new ArrayList<>(assignments.getSecondAssignments().size()); // Store final parent distances: - for (DistanceEntry<E> ent : assignments.getFirstAssignments()) { + for(DistanceEntry<E> ent : assignments.getFirstAssignments()) { final E e = ent.getEntry(); e.setParentDistance(ent.getDistance()); entries1.add(e); } - for (DistanceEntry<E> ent : assignments.getSecondAssignments()) { + for(DistanceEntry<E> ent : assignments.getSecondAssignments()) { final E e = ent.getEntry(); e.setParentDistance(ent.getDistance()); entries2.add(e); @@ -319,14 +310,14 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends writeNode(node); writeNode(newNode); - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { String msg = "Split Node " + node.getPageID() + " (" + this.getClass() + ")\n" + " newNode " + newNode.getPageID() + "\n" + " firstPromoted " + assignments.getFirstRoutingObject() + "\n" + " firstAssignments(" + node.getPageID() + ") " + assignments.getFirstAssignments() + "\n" + " firstCR " + assignments.getFirstCoveringRadius() + "\n" + " secondPromoted " + assignments.getSecondRoutingObject() + "\n" + " secondAssignments(" + newNode.getPageID() + ") " + assignments.getSecondAssignments() + "\n" + " secondCR " + assignments.getSecondCoveringRadius() + "\n"; getLogger().debugFine(msg); } // if root was split: create a new root that points the two split // nodes - if (isRoot(node)) { + if(isRoot(node)) { // FIXME: stimmen die parentDistance der Kinder in node & splitNode? IndexTreePath<E> newRootPath = createNewRoot(node, newNode, assignments.getFirstRoutingObject(), assignments.getSecondRoutingObject()); adjustTree(newRootPath); @@ -336,16 +327,16 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends // get the parent and add the new split node E parentEntry = subtree.getParentPath().getLastPathComponent().getEntry(); N parent = getNode(parentEntry); - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { getLogger().debugFine("parent " + parent); } - double parentDistance2 = distance(parentEntry.getRoutingObjectID(), assignments.getSecondRoutingObject()).doubleValue(); + double parentDistance2 = distance(parentEntry.getRoutingObjectID(), assignments.getSecondRoutingObject()); // logger.warning("parent: "+parent.toString()+" split: " + // splitNode.toString()+ " dist:"+parentDistance2); parent.addDirectoryEntry(createNewDirectoryEntry(newNode, assignments.getSecondRoutingObject(), parentDistance2)); // adjust the entry representing the (old) node, that has been split - double parentDistance1 = distance(parentEntry.getRoutingObjectID(), assignments.getFirstRoutingObject()).doubleValue(); + double parentDistance1 = distance(parentEntry.getRoutingObjectID(), assignments.getFirstRoutingObject()); // logger.warning("parent: "+parent.toString()+" node: " + // node.toString()+ " dist:"+parentDistance1); node.adjustEntry(parent.getEntry(nodeIndex), assignments.getFirstRoutingObject(), parentDistance1, this); @@ -358,7 +349,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends // no overflow, only adjust parameters of the entry representing the // node else { - if (!isRoot(node)) { + if(!isRoot(node)) { E parentEntry = subtree.getParentPath().getLastPathComponent().getEntry(); N parent = getNode(parentEntry); int index = subtree.getLastPathComponent().getIndex(); @@ -385,7 +376,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * otherwise */ private boolean hasOverflow(N node) { - if (node.isLeaf()) { + if(node.isLeaf()) { return node.getNumEntries() == leafCapacity; } @@ -411,9 +402,9 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends // switch the ids oldRoot.setPageID(root.getPageID()); - if (!oldRoot.isLeaf()) { + if(!oldRoot.isLeaf()) { // FIXME: what is happening here? - for (int i = 0; i < oldRoot.getNumEntries(); i++) { + for(int i = 0; i < oldRoot.getNumEntries(); i++) { N node = getNode(oldRoot.getEntry(i)); writeNode(node); } @@ -437,7 +428,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends writeNode(root); writeNode(oldRoot); writeNode(newNode); - if (getLogger().isDebugging()) { + if(getLogger().isDebugging()) { String msg = "Create new Root: ID=" + root.getPageID(); msg += "\nchild1 " + oldRoot; msg += "\nchild2 " + newNode; @@ -451,13 +442,13 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends public List<E> getLeaves() { List<E> result = new ArrayList<>(); BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<>(this, getRootPath()); - while (enumeration.hasMoreElements()) { + while(enumeration.hasMoreElements()) { IndexTreePath<E> path = enumeration.nextElement(); E entry = path.getLastPathComponent().getEntry(); - if (!entry.isLeafEntry()) { + if(!entry.isLeafEntry()) { // TODO: any way to skip unnecessary reads? N node = getNode(entry); - if (node.isLeaf()) { + if(node.isLeaf()) { result.add(entry); } } @@ -474,8 +465,8 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends int levels = 0; N node = getRoot(); - while (!node.isLeaf()) { - if (node.getNumEntries() > 0) { + while(!node.isLeaf()) { + if(node.getNumEntries() > 0) { E entry = node.getEntry(0); node = getNode(entry); levels++; @@ -488,7 +479,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends public void logStatistics() { super.logStatistics(); Logging log = getLogger(); - if (log.isStatistics()) { + if(log.isStatistics()) { log.statistics(new LongStatistic(this.getClass().getName() + ".height", getHeight())); statistics.logStatistics(); } @@ -532,7 +523,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * Count a distance computation. */ public void countDistanceCalculation() { - if (distanceCalcs != null) { + if(distanceCalcs != null) { distanceCalcs.increment(); } } @@ -541,7 +532,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * Count a knn query invocation. */ public void countKNNQuery() { - if (knnQueries != null) { + if(knnQueries != null) { knnQueries.increment(); } } @@ -550,7 +541,7 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends * Count a range query invocation. */ public void countRangeQuery() { - if (rangeQueries != null) { + if(rangeQueries != null) { rangeQueries.increment(); } } @@ -560,13 +551,13 @@ public abstract class AbstractMTree<O, D extends NumberDistance<D, ?>, N extends */ public void logStatistics() { Logging log = getLogger(); - if (statistics.distanceCalcs != null) { + if(statistics.distanceCalcs != null) { log.statistics(statistics.distanceCalcs); } - if (statistics.knnQueries != null) { + if(statistics.knnQueries != null) { log.statistics(statistics.knnQueries); } - if (statistics.rangeQueries != null) { + if(statistics.rangeQueries != null) { log.statistics(statistics.rangeQueries); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java index 7a0baa8a..458bf96b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.Index; import de.lmu.ifi.dbs.elki.index.PagedIndexFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert.MTreeInsert; @@ -48,12 +47,11 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * @apiviz.excludeSubtypes * * @param <O> Object type - * @param <D> Distance type * @param <N> Node type * @param <E> Entry type * @param <I> Index type */ -public abstract class AbstractMTreeFactory<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, I extends AbstractMTree<O, D, N, E, S> & Index, S extends MTreeSettings<O, D, N, E>> extends PagedIndexFactory<O, I> { +public abstract class AbstractMTreeFactory<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, I extends AbstractMTree<O, N, E, S> & Index, S extends MTreeSettings<O, N, E>> extends PagedIndexFactory<O, I> { /** * Tree settings. */ @@ -82,7 +80,7 @@ public abstract class AbstractMTreeFactory<O, D extends NumberDistance<D, ?>, N * * @apiviz.exclude */ - public abstract static class Parameterizer<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, D, N, E>> extends PagedIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, N, E>> extends PagedIndexFactory.Parameterizer<O> { /** * Parameter to specify the distance function to determine the distance * between database objects, must extend @@ -122,15 +120,15 @@ public abstract class AbstractMTreeFactory<O, D extends NumberDistance<D, ?>, N protected void makeOptions(Parameterization config) { super.makeOptions(config); settings = makeSettings(); - ObjectParameter<DistanceFunction<O, D>> distanceFunctionP = new ObjectParameter<>(DISTANCE_FUNCTION_ID, DistanceFunction.class, EuclideanDistanceFunction.class); + ObjectParameter<DistanceFunction<O>> distanceFunctionP = new ObjectParameter<>(DISTANCE_FUNCTION_ID, DistanceFunction.class, EuclideanDistanceFunction.class); if (config.grab(distanceFunctionP)) { settings.distanceFunction = distanceFunctionP.instantiateClass(config); } - ObjectParameter<MTreeSplit<O, D, N, E>> splitStrategyP = new ObjectParameter<>(SPLIT_STRATEGY_ID, MTreeSplit.class, MMRadSplit.class); + ObjectParameter<MTreeSplit<O, N, E>> splitStrategyP = new ObjectParameter<>(SPLIT_STRATEGY_ID, MTreeSplit.class, MMRadSplit.class); if (config.grab(splitStrategyP)) { settings.splitStrategy = splitStrategyP.instantiateClass(config); } - ObjectParameter<MTreeInsert<O, D, N, E>> insertStrategyP = new ObjectParameter<>(INSERT_STRATEGY_ID, MTreeInsert.class, MinimumEnlargementInsert.class); + ObjectParameter<MTreeInsert<O, N, E>> insertStrategyP = new ObjectParameter<>(INSERT_STRATEGY_ID, MTreeInsert.class, MinimumEnlargementInsert.class); if (config.grab(insertStrategyP)) { settings.insertStrategy = insertStrategyP.instantiateClass(config); } @@ -139,6 +137,6 @@ public abstract class AbstractMTreeFactory<O, D extends NumberDistance<D, ?>, N abstract protected S makeSettings(); @Override - protected abstract AbstractMTreeFactory<O, D, N, E, ?, ?> makeInstance(); + protected abstract AbstractMTreeFactory<O, N, E, ?, ?> makeInstance(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeNode.java index 1c1f486c..98b51b44 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; import java.util.logging.Logger; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.AbstractNode; import de.lmu.ifi.dbs.elki.logging.LoggingConfiguration; @@ -39,11 +38,10 @@ import de.lmu.ifi.dbs.elki.logging.LoggingConfiguration; * @apiviz.excludeSubtypes * * @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 AbstractMTreeNode<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends AbstractNode<E> { +public abstract class AbstractMTreeNode<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends AbstractNode<E> { /** * Empty constructor for Externalizable interface. */ @@ -73,14 +71,14 @@ public abstract class AbstractMTreeNode<O, D extends NumberDistance<D, ?>, N ext * the routing object of the parent node * @param mTree the M-Tree object holding this node */ - public void adjustEntry(E entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, D, N, E, ?> mTree) { + public void adjustEntry(E entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, N, E, ?> mTree) { entry.setRoutingObjectID(routingObjectID); entry.setParentDistance(parentDistance); entry.setCoveringRadius(coveringRadius(entry.getRoutingObjectID(), mTree)); for (int i = 0; i < getNumEntries(); i++) { E childEntry = getEntry(i); - double dist = mTree.distance(routingObjectID, childEntry.getRoutingObjectID()).doubleValue(); + double dist = mTree.distance(routingObjectID, childEntry.getRoutingObjectID()); childEntry.setParentDistance(dist); } } @@ -92,11 +90,11 @@ public abstract class AbstractMTreeNode<O, D extends NumberDistance<D, ?>, N ext * @param mTree the M-Tree * @return the covering radius of this node */ - public double coveringRadius(DBID routingObjectID, AbstractMTree<O, D, N, E, ?> mTree) { + public double coveringRadius(DBID routingObjectID, AbstractMTree<O, N, E, ?> mTree) { double coveringRadius = 0.; for (int i = 0; i < getNumEntries(); i++) { E entry = getEntry(i); - double distance = mTree.distance(entry.getRoutingObjectID(), routingObjectID).doubleValue() + entry.getCoveringRadius(); + double distance = mTree.distance(entry.getRoutingObjectID(), routingObjectID) + entry.getCoveringRadius(); coveringRadius = Math.max(coveringRadius, distance); } return coveringRadius; @@ -109,7 +107,7 @@ public abstract class AbstractMTreeNode<O, D extends NumberDistance<D, ?>, N ext * @param entry the entry representing this node */ @SuppressWarnings("unchecked") - public final void integrityCheck(AbstractMTree<O, D, N, E, ?> mTree, E entry) { + public final void integrityCheck(AbstractMTree<O, N, E, ?> mTree, E entry) { // leaf node if (isLeaf()) { for (int i = 0; i < getCapacity(); i++) { @@ -174,10 +172,10 @@ public abstract class AbstractMTreeNode<O, D extends NumberDistance<D, ?>, N ext * @param index the index of the entry in the parents child arry * @param mTree the M-Tree holding this node */ - protected void integrityCheckParameters(E parentEntry, N parent, int index, AbstractMTree<O, D, N, E, ?> mTree) { + protected void integrityCheckParameters(E parentEntry, N parent, int index, AbstractMTree<O, N, E, ?> mTree) { // test if parent distance is correctly set E entry = parent.getEntry(index); - double parentDistance = mTree.distance(entry.getRoutingObjectID(), parentEntry.getRoutingObjectID()).doubleValue(); + double parentDistance = mTree.distance(entry.getRoutingObjectID(), parentEntry.getRoutingObjectID()); if (Math.abs(entry.getParentDistance() - parentDistance) > 1E-10) { throw new RuntimeException("Wrong parent distance in node " + parent.getPageID() + " at index " + index + " (child " + entry + ")" + "\nsoll: " + parentDistance + ",\n ist: " + entry.getParentDistance()); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java index 92d0a7ea..ea2cd416 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 @@ -66,7 +66,7 @@ public class MTreeDirectoryEntry extends AbstractDirectoryEntry implements MTree } /** - * Provides a new MTreeDirectoryEntry with the given parameters. + * Constructor. * * @param objectID the id of the routing object * @param parentDistance the distance from the routing object of this entry to diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeEntry.java index 66628087..ebae6a4f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeLeafEntry.java index cfb22bac..c53cc4d6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 @@ -58,7 +58,7 @@ public class MTreeLeafEntry extends AbstractLeafEntry implements MTreeEntry { } /** - * Provides a new MTreeLeafEntry object with the given parameters. + * Constructor. * * @param objectID the id of the underlying data object * @param parentDistance the distance from the underlying data object to its diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeSettings.java index 59f6e598..46a0851a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeSettings.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeSettings.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; */ import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert.MTreeInsert; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MTreeSplit; @@ -34,23 +33,22 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MT * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type * @param <N> Node type * @param <E> Entry type */ -public class MTreeSettings<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> { +public class MTreeSettings<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> { /** * Holds the instance of the trees distance function. */ - protected DistanceFunction<? super O, D> distanceFunction; + protected DistanceFunction<? super O> distanceFunction; /** * Splitting strategy. */ - protected MTreeSplit<O, D, N, E> splitStrategy; + protected MTreeSplit<O, N, E> splitStrategy; /** * Insertion strategy. */ - protected MTreeInsert<O, D, N, E> insertStrategy; + protected MTreeInsert<O, N, E> insertStrategy; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java index aec4410e..2f71f540 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; 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 @@ -31,12 +31,11 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; -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; @@ -51,21 +50,20 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @author Elke Achtert * @param <O> the type of DatabaseObject to be stored in the metrical index - * @param <D> the type of Distance used in the metrical index * @param <N> the type of MetricalNode used in the metrical index * @param <E> the type of MetricalEntry used in the metrical index * @param <S> the type of Settings kept. */ -public abstract class AbstractMkTree<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, D, N, E>> extends AbstractMTree<O, D, N, E, S> { +public abstract class AbstractMkTree<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, S extends MTreeSettings<O, N, E>> extends AbstractMTree<O, N, E, S> { /** * Internal class for performing knn queries */ - protected KNNQuery<O, D> knnq; + protected KNNQuery<O> knnq; /** * Distance query to use. */ - private DistanceQuery<O, D> distanceQuery; + private DistanceQuery<O> distanceQuery; /** * Constructor. @@ -82,9 +80,9 @@ public abstract class AbstractMkTree<O, D extends NumberDistance<D, ?>, N extend } @Override - public D distance(DBIDRef id1, DBIDRef id2) { - if (id1 == null || id2 == null) { - return getDistanceFactory().undefinedDistance(); + public double distance(DBIDRef id1, DBIDRef id2) { + if(id1 == null || id2 == null) { + return Double.NaN; } statistics.countDistanceCalculation(); return distanceQuery.distance(id1, id2); @@ -98,7 +96,7 @@ public abstract class AbstractMkTree<O, D extends NumberDistance<D, ?>, N extend * @param k the number of nearest neighbors to be returned * @return a List of the query results */ - public abstract DistanceDBIDList<D> reverseKNNQuery(final DBIDRef id, int k); + public abstract DoubleDBIDList reverseKNNQuery(final DBIDRef id, int k); /** * Performs a batch k-nearest neighbor query for a list of query objects. @@ -111,9 +109,9 @@ public abstract class AbstractMkTree<O, D extends NumberDistance<D, ?>, N extend * @deprecated Change to use by-object NN lookups instead. */ @Deprecated - protected final Map<DBID, KNNList<D>> batchNN(N node, DBIDs ids, int kmax) { - Map<DBID, KNNList<D>> res = new HashMap<>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + protected final Map<DBID, KNNList> batchNN(N node, DBIDs ids, int kmax) { + Map<DBID, KNNList> res = new HashMap<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); res.put(id, knnq.getKNNForDBID(id, kmax)); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java index 455d372a..4c43e667 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; 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 @@ -28,10 +28,9 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; @@ -48,12 +47,11 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @apiviz.composedOf MkTreeSettings * * @param <O> the type of DatabaseObject to be stored in the metrical index - * @param <D> the type of Distance used in the metrical index * @param <N> the type of MetricalNode used in the metrical index * @param <E> the type of MetricalEntry used in the metrical index * @param <S> the type of Settings used. */ -public abstract class AbstractMkTreeUnified<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, S extends MkTreeSettings<O, D, N, E>> extends AbstractMkTree<O, D, N, E, S> { +public abstract class AbstractMkTreeUnified<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, S extends MkTreeSettings<O, N, E>> extends AbstractMkTree<O, N, E, S> { /** * Constructor. * @@ -92,7 +90,7 @@ public abstract class AbstractMkTreeUnified<O, D extends NumberDistance<D, ?>, N } // do batch nn - Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), ids, settings.k_max); + Map<DBID, KNNList> knnLists = batchNN(getRoot(), ids, settings.k_max); // adjust the knn distances kNNdistanceAdjustment(getRootEntry(), knnLists); @@ -108,7 +106,7 @@ public abstract class AbstractMkTreeUnified<O, D extends NumberDistance<D, ?>, N * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - protected abstract void kNNdistanceAdjustment(E entry, Map<DBID, KNNList<D>> knnLists); + protected abstract void kNNdistanceAdjustment(E entry, Map<DBID, KNNList> knnLists); /** * Get the value of k_max. diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java index 996b2438..9997713d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.Index; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; @@ -43,12 +42,11 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; * @apiviz.uses AbstractMkTreeUnified oneway - - «create» * * @param <O> Object type - * @param <D> Distance type * @param <N> Node type * @param <E> Entry type * @param <I> Index type */ -public abstract class AbstractMkTreeUnifiedFactory<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, I extends AbstractMkTree<O, D, N, E, S> & Index, S extends MkTreeSettings<O, D, N, E>> extends AbstractMTreeFactory<O, D, N, E, I, S> { +public abstract class AbstractMkTreeUnifiedFactory<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, I extends AbstractMkTree<O, N, E, S> & Index, S extends MkTreeSettings<O, N, E>> extends AbstractMTreeFactory<O, N, E, I, S> { /** * Constructor. * @@ -66,7 +64,7 @@ public abstract class AbstractMkTreeUnifiedFactory<O, D extends NumberDistance<D * * @apiviz.exclude */ - public abstract static class Parameterizer<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry, S extends MkTreeSettings<O, D, N, E>> extends AbstractMTreeFactory.Parameterizer<O, D, N, E, S> { + public abstract static class Parameterizer<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry, S extends MkTreeSettings<O, N, E>> extends AbstractMTreeFactory.Parameterizer<O, N, E, S> { /** * Parameter specifying the maximal number k of reverse k nearest neighbors * to be supported, must be an integer greater than 0. @@ -88,6 +86,6 @@ public abstract class AbstractMkTreeUnifiedFactory<O, D extends NumberDistance<D } @Override - protected abstract AbstractMkTreeUnifiedFactory<O, D, N, E, ?, S> makeInstance(); + protected abstract AbstractMkTreeUnifiedFactory<O, N, E, ?, S> makeInstance(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeHeader.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeHeader.java index ff49d789..47f0eda0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeHeader.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeHeader.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeSettings.java index 6a957bd7..8d5fa450 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeSettings.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/MkTreeSettings.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeSettings; @@ -34,11 +33,10 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeSettings; * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type * @param <N> Node type * @param <E> Entry type */ -public class MkTreeSettings<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends MTreeSettings<O, D, N, E> { +public class MkTreeSettings<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends MTreeSettings<O, N, E> { /** * Holds the maximum value of k to support. */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppDirectoryEntry.java index fd6f6bab..89d0cba1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -56,7 +56,7 @@ class MkAppDirectoryEntry extends MTreeDirectoryEntry implements MkAppEntry { } /** - * Provides a new MkCoPDirectoryEntry with the given parameters. + * Constructor. * * @param objectID the id of the routing object * @param parentDistance the distance from the object to its parent diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppEntry.java index 5424f6f1..54cfcc29 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppLeafEntry.java index e1f2305a..c2f81af2 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -56,7 +56,7 @@ class MkAppLeafEntry extends MTreeLeafEntry implements MkAppEntry { } /** - * Provides a new MkAppLeafEntry with the given parameters. + * Constructor. * * @param objectID the id of the underlying data object * @param parentDistance the distance from the underlying data object to its diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java index 1ff0a030..41a83fcf 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.List; import java.util.Map; @@ -33,22 +32,21 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.statistics.PolynomialRegression; -import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; /** * MkAppTree is a metrical index structure based on the concepts of the M-Tree @@ -61,9 +59,8 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; * @apiviz.has MkAppTreeNode oneway - - contains * * @param <O> the type of DatabaseObject to be stored in the metrical index - * @param <D> the type of NumberDistance used in the metrical index */ -public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree<O, D, MkAppTreeNode<O, D>, MkAppEntry, MkAppTreeSettings<O, D>> { +public class MkAppTree<O> extends AbstractMkTree<O, MkAppTreeNode<O>, MkAppEntry, MkAppTreeSettings<O>> { /** * The logger for this class. */ @@ -76,7 +73,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param pageFile Page file * @param settings Tree settings */ - public MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O, D>> pageFile, MkAppTreeSettings<O, D> settings) { + public MkAppTree(Relation<O> relation, PageFile<MkAppTreeNode<O>> pageFile, MkAppTreeSettings<O> settings) { super(relation, pageFile, settings); } @@ -103,34 +100,34 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree */ @Override public void insertAll(List<MkAppEntry> entries) { - if (entries.isEmpty()) { + if(entries.isEmpty()) { return; } - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { LOG.debugFine("insert " + entries + "\n"); } - if (!initialized) { + if(!initialized) { initialize(entries.get(0)); } ModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); // insert - for (MkAppEntry entry : entries) { + for(MkAppEntry entry : entries) { ids.add(entry.getRoutingObjectID()); // insert the object super.insert(entry, false); } // do batch nn - Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), ids, settings.k_max + 1); + Map<DBID, KNNList> knnLists = batchNN(getRoot(), ids, settings.k_max + 1); // adjust the knn distances adjustApproximatedKNNDistances(getRootEntry(), knnLists); - if (EXTRA_INTEGRITY_CHECKS) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -144,49 +141,48 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k) { - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k) { + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); final Heap<GenericMTreeDistanceSearchCandidate> pq = new UpdatableHeap<>(); // push root pq.add(new GenericMTreeDistanceSearchCandidate(0., getRootID(), null)); // search in tree - while (!pq.isEmpty()) { + while(!pq.isEmpty()) { GenericMTreeDistanceSearchCandidate pqNode = pq.poll(); // FIXME: cache the distance to the routing object in the queue node! - MkAppTreeNode<O, D> node = getNode(pqNode.nodeID); + MkAppTreeNode<O> node = getNode(pqNode.nodeID); // directory node - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(!node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkAppEntry entry = node.getEntry(i); - double distance = distance(entry.getRoutingObjectID(), id).doubleValue(); + double distance = distance(entry.getRoutingObjectID(), id); double minDist = (entry.getCoveringRadius() > distance) ? 0. : distance - entry.getCoveringRadius(); double approxValue = settings.log ? Math.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); - if (approxValue < 0) { + if(approxValue < 0) { approxValue = 0; } - if (minDist <= approxValue) { + if(minDist <= approxValue) { pq.add(new GenericMTreeDistanceSearchCandidate(minDist, getPageID(entry), entry.getRoutingObjectID())); } } } // data node else { - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { MkAppLeafEntry entry = (MkAppLeafEntry) node.getEntry(i); - D distance = distance(entry.getRoutingObjectID(), id); + double distance = distance(entry.getRoutingObjectID(), id); double approxValue = settings.log ? StrictMath.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); - if (approxValue < 0) { + if(approxValue < 0) { approxValue = 0; } - D approximatedKnnDist = getDistanceFactory().fromDouble(approxValue); - if (distance.compareTo(approximatedKnnDist) <= 0) { + if(distance <= approxValue) { result.add(distance, entry.getRoutingObjectID()); } } @@ -213,7 +209,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // overhead = index(4), numEntries(4), id(4), isLeaf(0.125) double overhead = 12.125; - if (getPageSize() - overhead < 0) { + if(getPageSize() - overhead < 0) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } @@ -221,11 +217,11 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // coveringRadius + parentDistance + approx) + 1 dirCapacity = (int) (getPageSize() - overhead) / (4 + 4 + distanceSize + distanceSize + (settings.p + 1) * 4 + 2) + 1; - if (dirCapacity <= 1) { + if(dirCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (dirCapacity < 10) { + if(dirCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } @@ -234,39 +230,37 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // approx) + 1 leafCapacity = (int) (getPageSize() - overhead) / (4 + distanceSize + (settings.p + 1) * 4 + 2) + 1; - if (leafCapacity <= 1) { + if(leafCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (leafCapacity < 10) { + if(leafCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } initialized = true; - if (LOG.isVerbose()) { + if(LOG.isVerbose()) { LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); } } - private List<D> getMeanKNNList(DBIDs ids, Map<DBID, KNNList<D>> knnLists) { + private double[] getMeanKNNList(DBIDs ids, Map<DBID, KNNList> knnLists) { double[] means = new double[settings.k_max]; - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); - KNNList<D> knns = knnLists.get(id); + KNNList knns = knnLists.get(id); int k = 0; - for (DistanceDBIDListIter<D> it = knns.iter(); k < settings.k_max && it.valid(); it.advance(), k++) { - means[k] += it.getDistance().doubleValue(); + for(DoubleDBIDListIter it = knns.iter(); k < settings.k_max && it.valid(); it.advance(), k++) { + means[k] += it.doubleValue(); } } - List<D> result = new ArrayList<>(); - for (int k = 0; k < settings.k_max; k++) { + for(int k = 0; k < settings.k_max; k++) { means[k] /= ids.size(); - result.add(getDistanceFactory().fromDouble(means[k])); } - return result; + return means; } /** @@ -275,19 +269,20 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - private void adjustApproximatedKNNDistances(MkAppEntry entry, Map<DBID, KNNList<D>> knnLists) { - MkAppTreeNode<O, D> node = getNode(entry); + private void adjustApproximatedKNNDistances(MkAppEntry entry, Map<DBID, KNNList> knnLists) { + MkAppTreeNode<O> node = getNode(entry); - if (node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkAppLeafEntry leafEntry = (MkAppLeafEntry) node.getEntry(i); // approximateKnnDistances(leafEntry, // getKNNList(leafEntry.getRoutingObjectID(), knnLists)); PolynomialApproximation approx = approximateKnnDistances(getMeanKNNList(leafEntry.getDBID(), knnLists)); leafEntry.setKnnDistanceApproximation(approx); } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { MkAppEntry dirEntry = node.getEntry(i); adjustApproximatedKNNDistances(dirEntry, knnLists); } @@ -307,15 +302,16 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param result the result list containing the ids of the leaf entries stored * in the specified subtree */ - private void leafEntryIDs(MkAppTreeNode<O, D> node, ModifiableDBIDs result) { - if (node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + private void leafEntryIDs(MkAppTreeNode<O> node, ModifiableDBIDs result) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkAppEntry entry = node.getEntry(i); result.add(((LeafEntry) entry).getDBID()); } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { - MkAppTreeNode<O, D> childNode = getNode(node.getEntry(i)); + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { + MkAppTreeNode<O> childNode = getNode(node.getEntry(i)); leafEntryIDs(childNode, result); } } @@ -327,17 +323,18 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param knnDistances the knn-distances of the leaf entry * @return the polynomial approximation of the specified knn-distances. */ - private PolynomialApproximation approximateKnnDistances(List<D> knnDistances) { + private PolynomialApproximation approximateKnnDistances(double[] knnDistances) { StringBuilder msg = new StringBuilder(); // count the zero distances (necessary of log-log space is used) int k_0 = 0; - if (settings.log) { - for (int i = 0; i < settings.k_max; i++) { - double dist = knnDistances.get(i).doubleValue(); - if (dist == 0) { + if(settings.log) { + for(int i = 0; i < settings.k_max; i++) { + double dist = knnDistances[i]; + if(dist == 0) { k_0++; - } else { + } + else { break; } } @@ -346,20 +343,21 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree de.lmu.ifi.dbs.elki.math.linearalgebra.Vector x = new de.lmu.ifi.dbs.elki.math.linearalgebra.Vector(settings.k_max - k_0); de.lmu.ifi.dbs.elki.math.linearalgebra.Vector y = new de.lmu.ifi.dbs.elki.math.linearalgebra.Vector(settings.k_max - k_0); - for (int k = 0; k < settings.k_max - k_0; k++) { - if (settings.log) { + for(int k = 0; k < settings.k_max - k_0; k++) { + if(settings.log) { x.set(k, Math.log(k + k_0)); - y.set(k, Math.log(knnDistances.get(k + k_0).doubleValue())); - } else { + y.set(k, Math.log(knnDistances[k + k_0])); + } + else { x.set(k, k + k_0); - y.set(k, knnDistances.get(k + k_0).doubleValue()); + y.set(k, knnDistances[k + k_0]); } } PolynomialRegression regression = new PolynomialRegression(y, x, settings.p); PolynomialApproximation approximation = new PolynomialApproximation(regression.getEstimatedCoefficients().getArrayCopy()); - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { msg.append("approximation ").append(approximation); LOG.debugFine(msg.toString()); } @@ -373,7 +371,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new leaf node */ @Override - protected MkAppTreeNode<O, D> createNewLeafNode() { + protected MkAppTreeNode<O> createNewLeafNode() { return new MkAppTreeNode<>(leafCapacity, true); } @@ -383,7 +381,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new directory node */ @Override - protected MkAppTreeNode<O, D> createNewDirectoryNode() { + protected MkAppTreeNode<O> createNewDirectoryNode() { return new MkAppTreeNode<>(dirCapacity, false); } @@ -396,7 +394,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * the routing object of the parent node */ @Override - protected MkAppEntry createNewDirectoryEntry(MkAppTreeNode<O, D> node, DBID routingObjectID, double parentDistance) { + protected MkAppEntry createNewDirectoryEntry(MkAppTreeNode<O> node, DBID routingObjectID, double parentDistance) { return new MkAppDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this), null); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java index 1d4b7fe4..0bffdd29 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; */ import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeFactory; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; @@ -44,9 +43,8 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; * @apiviz.uses MkAppTreeIndex oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory<O, D, MkAppTreeNode<O, D>, MkAppEntry, MkAppTreeIndex<O, D>, MkAppTreeSettings<O, D>> { +public class MkAppTreeFactory<O> extends AbstractMTreeFactory<O, MkAppTreeNode<O>, MkAppEntry, MkAppTreeIndex<O>, MkAppTreeSettings<O>> { /** * Parameter for nolog */ @@ -68,17 +66,17 @@ public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * @param pageFileFactory Data storage * @param settings Tree settings */ - public MkAppTreeFactory(PageFileFactory<?> pageFileFactory, MkAppTreeSettings<O, D> settings) { + public MkAppTreeFactory(PageFileFactory<?> pageFileFactory, MkAppTreeSettings<O> settings) { super(pageFileFactory, settings); } @Override - public MkAppTreeIndex<O, D> instantiate(Relation<O> relation) { - PageFile<MkAppTreeNode<O, D>> pagefile = makePageFile(getNodeClass()); + public MkAppTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<MkAppTreeNode<O>> pagefile = makePageFile(getNodeClass()); return new MkAppTreeIndex<>(relation, pagefile, settings); } - protected Class<MkAppTreeNode<O, D>> getNodeClass() { + protected Class<MkAppTreeNode<O>> getNodeClass() { return ClassGenericsUtil.uglyCastIntoSubclass(MkAppTreeNode.class); } @@ -88,8 +86,10 @@ public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type */ - public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory.Parameterizer<O, D, MkAppTreeNode<O, D>, MkAppEntry, MkAppTreeSettings<O, D>> { + public static class Parameterizer<O> extends AbstractMTreeFactory.Parameterizer<O, MkAppTreeNode<O>, MkAppEntry, MkAppTreeSettings<O>> { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); @@ -112,12 +112,12 @@ public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac } @Override - protected MkAppTreeFactory<O, D> makeInstance() { + protected MkAppTreeFactory<O> makeInstance() { return new MkAppTreeFactory<>(pageFileFactory, settings); } @Override - protected MkAppTreeSettings<O, D> makeSettings() { + protected MkAppTreeSettings<O> makeSettings() { return new MkAppTreeSettings<>(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java index 2a630bf0..5db5d03c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -36,8 +36,6 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -51,9 +49,8 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type */ -public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree<O, D> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { +public class MkAppTreeIndex<O> extends MkAppTree<O> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { /** * The relation indexed */ @@ -66,7 +63,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree * @param pageFile Page file * @param settings Tree settings */ - public MkAppTreeIndex(Relation<O> relation, PageFile<MkAppTreeNode<O, D>> pageFile, MkAppTreeSettings<O, D> settings) { + public MkAppTreeIndex(Relation<O> relation, PageFile<MkAppTreeNode<O>> pageFile, MkAppTreeSettings<O> settings) { super(relation, pageFile, settings); this.relation = relation; } @@ -95,14 +92,13 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree insertAll(objs); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> KNNQuery<O, S> getKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -115,18 +111,16 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (KNNQuery<O, S>) MTreeQueryUtil.getKNNQuery(this, dq, hints); + return MTreeQueryUtil.getKNNQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RangeQuery<O, S> getRangeQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -139,14 +133,12 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RangeQuery<O, S>) MTreeQueryUtil.getRangeQuery(this, dq, hints); + return MTreeQueryUtil.getRangeQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RKNNQuery<O, S> getRKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -159,8 +151,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RKNNQuery<O, S>) new MkTreeRKNNQuery<>(this, dq); + return (RKNNQuery<O>) new MkTreeRKNNQuery<>(this, distanceQuery); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java index 29609274..e9eb66b3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -27,7 +27,6 @@ import java.util.Arrays; import java.util.logging.Logger; import de.lmu.ifi.dbs.elki.database.ids.DBID; -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.logging.LoggingConfiguration; @@ -41,9 +40,8 @@ import de.lmu.ifi.dbs.elki.utilities.FormatUtil; * @apiviz.has MkAppEntry oneway - - contains * * @param <O> object type - * @param <D> distance type */ -class MkAppTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode<O, D, MkAppTreeNode<O, D>, MkAppEntry> { +class MkAppTreeNode<O> extends AbstractMTreeNode<O, MkAppTreeNode<O>, MkAppEntry> { private static final long serialVersionUID = 2; /** @@ -92,7 +90,7 @@ class MkAppTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode if(LoggingConfiguration.DEBUG) { StringBuilder msg = new StringBuilder(); - msg.append("b " + FormatUtil.format(b, 4)); + msg.append("b " + FormatUtil.format(b, FormatUtil.NF4)); Logger.getLogger(this.getClass().getName()).fine(msg.toString()); } @@ -109,13 +107,13 @@ class MkAppTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode * @param mTree the M-Tree object holding this node */ @Override - public void adjustEntry(MkAppEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, D, MkAppTreeNode<O, D>, MkAppEntry, ?> mTree) { + public void adjustEntry(MkAppEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, MkAppTreeNode<O>, MkAppEntry, ?> mTree) { super.adjustEntry(entry, routingObjectID, parentDistance, mTree); // entry.setKnnDistanceApproximation(knnDistanceApproximation()); } @Override - protected void integrityCheckParameters(MkAppEntry parentEntry, MkAppTreeNode<O, D> parent, int index, AbstractMTree<O, D, MkAppTreeNode<O, D>, MkAppEntry, ?> mTree) { + protected void integrityCheckParameters(MkAppEntry parentEntry, MkAppTreeNode<O> parent, int index, AbstractMTree<O, MkAppTreeNode<O>, MkAppEntry, ?> mTree) { super.integrityCheckParameters(parentEntry, parent, index, mTree); MkAppEntry entry = parent.getEntry(index); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeSettings.java index b9e0b8aa..3871586e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeSettings.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeSettings.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; /** @@ -32,9 +31,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSetti * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type */ -public class MkAppTreeSettings<O, D extends NumberDistance<D, ?>> extends MkTreeSettings<O, D, MkAppTreeNode<O, D>, MkAppEntry> { +public class MkAppTreeSettings<O> extends MkTreeSettings<O, MkAppTreeNode<O>, MkAppEntry> { /** * Parameter p. */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java index f156c607..7d801a81 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/PolynomialApproximation.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; 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 @@ -28,7 +28,6 @@ import java.io.IOException; import java.io.ObjectInput; import java.io.ObjectOutput; -import de.lmu.ifi.dbs.elki.math.MathUtil; import de.lmu.ifi.dbs.elki.utilities.FormatUtil; /** @@ -149,6 +148,6 @@ public class PolynomialApproximation implements Externalizable { */ @Override public String toString() { - return FormatUtil.format(b, 4); + return FormatUtil.format(b, FormatUtil.NF4); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/package-info.java index 7b897fe3..c7597169 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ApproximationLine.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ApproximationLine.java index 318c437b..bae501f3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ApproximationLine.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ApproximationLine.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java index fe0e20b0..7cdb0728 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPDirectoryEntry.java index 8b6282a3..aeb8e0ce 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -56,7 +56,7 @@ class MkCoPDirectoryEntry extends MTreeDirectoryEntry implements MkCoPEntry { } /** - * Provides a new MkCoPDirectoryEntry with the given parameters. + * Constructor. * * @param objectID the id of the routing object * @param parentDistance the distance from the object to its parent diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPEntry.java index ae569d03..393a6c72 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPLeafEntry.java index 7d241eba..b4b78ec5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -61,7 +61,7 @@ class MkCoPLeafEntry extends MTreeLeafEntry implements MkCoPEntry { } /** - * Provides a new MkCoPLeafEntry with the given parameters. + * Constructor. * * @param objectID the id of the underlying data object * @param parentDistance the distance from the underlying data object to its diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java index b98d6821..126013b1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -31,21 +31,20 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate; import de.lmu.ifi.dbs.elki.logging.Logging; -import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.FormatUtil; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; /** * MkCopTree is a metrical index structure based on the concepts of the M-Tree @@ -58,9 +57,8 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; * @apiviz.has ConvexHull * * @param <O> Object type - * @param <D> Distance type */ -public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry>> { +public class MkCoPTree<O> extends AbstractMkTree<O, MkCoPTreeNode<O>, MkCoPEntry, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry>> { /** * The logger for this class. */ @@ -78,11 +76,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param pagefile Page file * @param settings Tree settings */ - public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> settings) { + public MkCoPTree(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pagefile, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry> settings) { super(relation, pagefile, settings); // init log k log_k = new double[settings.k_max]; - for (int k = 1; k <= settings.k_max; k++) { + for(int k = 1; k <= settings.k_max; k++) { log_k[k - 1] = Math.log(k); } } @@ -105,34 +103,34 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree @Override public void insertAll(List<MkCoPEntry> entries) { - if (entries.isEmpty()) { + if(entries.isEmpty()) { return; } - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { LOG.debugFine("insert " + entries + "\n"); } - if (!initialized) { + if(!initialized) { initialize(entries.get(0)); } ModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); // insert - for (MkCoPEntry entry : entries) { + for(MkCoPEntry entry : entries) { ids.add(entry.getRoutingObjectID()); // insert the object super.insert(entry, false); } // perform nearest neighbor queries - Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), ids, settings.k_max); + Map<DBID, KNNList> knnLists = batchNN(getRoot(), ids, settings.k_max); // adjust the knn distances adjustApproximatedKNNDistances(getRootEntry(), knnLists); - if (EXTRA_INTEGRITY_CHECKS) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -146,17 +144,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k) { - if (k > settings.k_max) { + public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k) { + if(k > settings.k_max) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MCop-Tree!"); } - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); ModifiableDBIDs candidates = DBIDUtil.newArray(); doReverseKNNQuery(k, id, result, candidates); // refinement of candidates - Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), candidates, k); + Map<DBID, KNNList> knnLists = batchNN(getRoot(), candidates, k); result.sort(); // Collections.sort(candidates); @@ -165,12 +163,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // rkNNStatistics.addCandidates(candidates.size()); // rkNNStatistics.addTrueHits(result.size()); - for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { DBID cid = DBIDUtil.deref(iter); - KNNList<D> cands = knnLists.get(cid); - for (DistanceDBIDListIter<D> iter2 = cands.iter(); iter2.valid(); iter2.advance()) { - if (DBIDUtil.equal(id, iter2)) { - result.add(iter2.getDistance(), cid); + KNNList cands = knnLists.get(cid); + for(DoubleDBIDListIter iter2 = cands.iter(); iter2.valid(); iter2.advance()) { + if(DBIDUtil.equal(id, iter2)) { + result.add(iter2.doubleValue(), cid); break; } } @@ -200,7 +198,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // overhead = index(4), numEntries(4), id(4), isLeaf(0.125) double overhead = 12.125; - if (getPageSize() - overhead < 0) { + if(getPageSize() - overhead < 0) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } @@ -208,11 +206,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // coveringRadius + parentDistance + consApprox) + 1 dirCapacity = (int) (getPageSize() - overhead) / (4 + 4 + distanceSize + distanceSize + 10) + 1; - if (dirCapacity <= 1) { + if(dirCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (dirCapacity < 10) { + if(dirCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } @@ -221,17 +219,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // consApprox + progrApprox) + 1 leafCapacity = (int) (getPageSize() - overhead) / (4 + distanceSize + 2 * 10) + 1; - if (leafCapacity <= 1) { + if(leafCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (leafCapacity < 10) { + if(leafCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } initialized = true; - if (LOG.isVerbose()) { + if(LOG.isVerbose()) { LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); } } @@ -245,45 +243,46 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param candidates holds possible candidates for the result (they need a * refinement) */ - private void doReverseKNNQuery(int k, DBIDRef q, GenericDistanceDBIDList<D> result, ModifiableDBIDs candidates) { + private void doReverseKNNQuery(int k, DBIDRef q, ModifiableDoubleDBIDList result, ModifiableDBIDs candidates) { final ComparableMinHeap<GenericMTreeDistanceSearchCandidate> pq = new ComparableMinHeap<>(); // push root pq.add(new GenericMTreeDistanceSearchCandidate(0., getRootID(), null)); // search in tree - while (!pq.isEmpty()) { + while(!pq.isEmpty()) { GenericMTreeDistanceSearchCandidate pqNode = pq.poll(); // FIXME: cache the distance to the routing object in the queue node! - MkCoPTreeNode<O, D> node = getNode(pqNode.nodeID); + MkCoPTreeNode<O> node = getNode(pqNode.nodeID); // directory node - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(!node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkCoPEntry entry = node.getEntry(i); - double distance = distance(entry.getRoutingObjectID(), q).doubleValue(); + double distance = distance(entry.getRoutingObjectID(), q); double minDist = entry.getCoveringRadius() > distance ? 0. : distance - entry.getCoveringRadius(); double approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k); - if (minDist <= approximatedKnnDist_cons) { + if(minDist <= approximatedKnnDist_cons) { pq.add(new GenericMTreeDistanceSearchCandidate(minDist, getPageID(entry), entry.getRoutingObjectID())); } } } // data node else { - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { MkCoPLeafEntry entry = (MkCoPLeafEntry) node.getEntry(i); - D distance = distance(entry.getRoutingObjectID(), q); + double distance = distance(entry.getRoutingObjectID(), q); double approximatedKnnDist_prog = entry.approximateProgressiveKnnDistance(k); - if (distance.doubleValue() <= approximatedKnnDist_prog) { + if(distance <= approximatedKnnDist_prog) { result.add(distance, entry.getRoutingObjectID()); - } else { + } + else { double approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k); - double diff = distance.doubleValue() - approximatedKnnDist_cons; - if (diff <= 1E-10) { + double diff = distance - approximatedKnnDist_cons; + if(diff <= 1E-10) { candidates.add(entry.getRoutingObjectID()); } } @@ -298,16 +297,17 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - private void adjustApproximatedKNNDistances(MkCoPEntry entry, Map<DBID, KNNList<D>> knnLists) { - MkCoPTreeNode<O, D> node = getNode(entry); + private void adjustApproximatedKNNDistances(MkCoPEntry entry, Map<DBID, KNNList> knnLists) { + MkCoPTreeNode<O> node = getNode(entry); - if (node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkCoPLeafEntry leafEntry = (MkCoPLeafEntry) node.getEntry(i); approximateKnnDistances(leafEntry, knnLists.get(leafEntry.getRoutingObjectID())); } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { MkCoPEntry dirEntry = node.getEntry(i); adjustApproximatedKNNDistances(dirEntry, knnLists); } @@ -323,7 +323,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree private double ssqerr(int k0, int kmax, double[] logk, double[] log_kDist, double m, double t) { int k = kmax - k0; double result = 0; - for (int i = 0; i < k; i++) { + for(int i = 0; i < k; i++) { // double h = log_kDist[i] - (m * (logk[i] - logk[0]) + t); ??? double h = log_kDist[i] - m * logk[i] - t; result += h * h; @@ -349,19 +349,20 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param knnDistances TODO: Spezialbehandlung fuer identische Punkte in DB * (insbes. Distanz 0) */ - private void approximateKnnDistances(MkCoPLeafEntry entry, KNNList<D> knnDistances) { + private void approximateKnnDistances(MkCoPLeafEntry entry, KNNList knnDistances) { StringBuilder msg = LOG.isDebugging() ? new StringBuilder() : null; - if (msg != null) { + if(msg != null) { msg.append("\nknnDistances ").append(knnDistances); } // count the zero distances int k_0 = 0; - for (int i = 0; i < settings.k_max; i++) { - double dist = knnDistances.get(i).getDistance().doubleValue(); - if (dist == 0) { + for(int i = 0; i < settings.k_max; i++) { + double dist = knnDistances.get(i).doubleValue(); + if(dist == 0) { k_0++; - } else { + } + else { break; } } @@ -374,8 +375,8 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double sum_log_k_kDist = 0; double[] log_kDist = new double[settings.k_max - k_0]; - for (int i = 0; i < settings.k_max - k_0; i++) { - double dist = knnDistances.get(i + k_0).getDistance().doubleValue(); + for(int i = 0; i < settings.k_max - k_0; i++) { + double dist = knnDistances.get(i + k_0).doubleValue(); log_kDist[i] = Math.log(dist); sum_log_kDist += log_kDist[i]; sum_log_k_kDist += log_kDist[i] * log_k[i]; @@ -384,12 +385,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double sum_log_k = 0; double sum_log_k2 = 0; // noinspection ForLoopReplaceableByForEach - for (int i = 0; i < log_k.length; i++) { + for(int i = 0; i < log_k.length; i++) { sum_log_k += log_k[i]; sum_log_k2 += (log_k[i] * log_k[i]); } - if (msg != null) { + if(msg != null) { msg.append("\nk_0 ").append(k_0); msg.append("\nk_max ").append(settings.k_max); msg.append("\nlog_k(").append(log_k.length).append(") ").append(FormatUtil.format(log_k)); @@ -412,12 +413,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double err1 = ssqerr(k_0, settings.k_max, log_k, log_kDist, conservative.getM(), conservative.getT()); double err2 = ssqerr(k_0, settings.k_max, log_k, log_kDist, c2.getM(), c2.getT()); - if (msg != null) { + if(msg != null) { msg.append("err1 ").append(err1); msg.append("err2 ").append(err2); } - if (err1 > err2 && err1 - err2 > 0.000000001) { + if(err1 > err2 && err1 - err2 > 0.000000001) { // if (err1 > err2) { StringBuilder warning = new StringBuilder(); @@ -431,7 +432,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree warning.append("\nconservative1 ").append(conservative); warning.append("\nconservative2 ").append(c2); - for (int i = 0; i < u; i++) { + for(int i = 0; i < u; i++) { warning.append("\nlog_k[").append(upperHull[i]).append("] = ").append(log_k[upperHull[i]]); warning.append("\nlog_kDist[").append(upperHull[i]).append("] = ").append(log_kDist[upperHull[i]]); } @@ -444,7 +445,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree entry.setConservativeKnnDistanceApproximation(conservative); entry.setProgressiveKnnDistanceApproximation(progressive); - if (msg != null) { + if(msg != null) { LOG.debugFine(msg.toString()); } } @@ -470,12 +471,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double low_m = 0.0; double low_t = 0.0; - for (int i = 1; i < l; i++) { + for(int i = 1; i < l; i++) { double cur_m = (log_kDist[lowerHull[i]] - log_kDist[lowerHull[i - 1]]) / (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]]); double cur_t = log_kDist[lowerHull[i]] - cur_m * log_k[lowerHull[i]]; double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t); msg.append(" Segment = ").append(i).append(" m = ").append(cur_m).append(" t = ").append(cur_t).append(" lowerror = ").append(cur_error).append("\n"); - if (cur_error < low_error) { + if(cur_error < low_error) { low_error = cur_error; low_m = cur_m; low_t = cur_t; @@ -484,13 +485,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // linear search on all points of the lower convex hull boolean is_right = true; // NEEDED FOR PROOF CHECK - for (int i = 0; i < l; i++) { + for(int i = 0; i < l; i++) { double cur_m = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, log_k[lowerHull[i]], log_kDist[lowerHull[i]], sum_log_k_kDist, sum_log_kDist); double cur_t = log_kDist[lowerHull[i]] - cur_m * log_k[lowerHull[i]]; // only valid if both neighboring points are underneath y=mx+t - if ((i == 0 || log_kDist[lowerHull[i - 1]] >= log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && (i == l - 1 || log_kDist[lowerHull[i + 1]] >= log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) { + if((i == 0 || log_kDist[lowerHull[i - 1]] >= log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && (i == l - 1 || log_kDist[lowerHull[i + 1]] >= log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) { double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t); - if (cur_error < low_error) { + if(cur_error < low_error) { low_error = cur_error; low_m = cur_m; low_t = cur_t; @@ -498,9 +499,9 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } // check proof of bisection search - if (!(i > 0 && log_kDist[lowerHull[i - 1]] < log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && !is_right) { + if(!(i > 0 && log_kDist[lowerHull[i - 1]] < log_kDist[lowerHull[i]] - cur_m * (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]])) && !is_right) { // warning("ERROR lower: The bisection search will not work properly !"); - if (!(i < l - 1 && log_kDist[lowerHull[i + 1]] < log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) { + if(!(i < l - 1 && log_kDist[lowerHull[i + 1]] < log_kDist[lowerHull[i]] + cur_m * (log_k[lowerHull[i + 1]] - log_k[lowerHull[i]]))) { is_right = false; } } @@ -519,14 +520,14 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree ApproximationLine approx = null; double error = Double.POSITIVE_INFINITY; - for (int i = 0; i < u - 1; i++) { + for(int i = 0; i < u - 1; i++) { int ii = upperHull[i]; int jj = upperHull[i + 1]; double current_m = (log_kDist[jj] - log_kDist[ii]) / (log_k[jj] - log_k[ii]); double current_t = log_kDist[ii] - current_m * log_k[ii]; ApproximationLine current_approx = new ApproximationLine(k_0, current_m, current_t); - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { msg.append("\nlog_kDist[").append(jj).append("] ").append(log_kDist[jj]); msg.append("\nlog_kDist[").append(ii).append("] ").append(log_kDist[ii]); msg.append("\nlog_k[").append(jj).append("] ").append(log_k[jj]); @@ -537,22 +538,22 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree boolean ok = true; double currentError = 0; - for (int k = k_0; k <= settings.k_max; k++) { + for(int k = k_0; k <= settings.k_max; k++) { double appDist = current_approx.getValueAt(k); - if (appDist < log_kDist[k - k_0] && log_kDist[k - k_0] - appDist > 0.000000001) { + if(appDist < log_kDist[k - k_0] && log_kDist[k - k_0] - appDist > 0.000000001) { ok = false; break; } currentError += (appDist - log_kDist[k - k_0]); } - if (ok && currentError < error) { + if(ok && currentError < error) { approx = current_approx; error = currentError; } } - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { msg.append("\nupper Approx ").append(approx); LOG.debugFine(msg.toString()); } @@ -570,7 +571,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree int k_0 = settings.k_max - upperHull.length + 1; int a = u / 2; - while (marked.size() != u) { + while(marked.size() != u) { marked.add(a); double x_a = log_k[upperHull[a]]; double y_a = log_kDist[upperHull[a]]; @@ -578,7 +579,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double m_a = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, x_a, y_a, sum_log_k_kDist, sum_log_kDist); double t_a = y_a - m_a * x_a; - if (msg != null) { + if(msg != null) { msg.append("\na=").append(a).append(" m_a=").append(m_a).append(", t_a=").append(t_a); msg.append("\n err ").append(ssqerr(k_0, settings.k_max, log_k, log_kDist, m_a, m_a)); } @@ -591,23 +592,24 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree boolean lessThanPre = a == 0 || y_p <= m_a * x_p + t_a; boolean lessThanSuc = a == u || y_s <= m_a * x_s + t_a; - if (lessThanPre && lessThanSuc) { + if(lessThanPre && lessThanSuc) { ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if (msg != null) { + if(msg != null) { msg.append("\n1 anchor = ").append(a); LOG.debugFine(msg.toString()); } return appr; - } else if (!lessThanPre) { - if (marked.contains(a - 1)) { + } + else if(!lessThanPre) { + if(marked.contains(a - 1)) { m_a = (y_a - y_p) / (x_a - x_p); - if (y_a == y_p) { + if(y_a == y_p) { m_a = 0; } t_a = y_a - m_a * x_a; ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if (msg != null) { + if(msg != null) { msg.append("2 anchor = ").append(a); msg.append(" appr1 ").append(appr); msg.append(" x_a ").append(x_a).append(", y_a ").append(y_a); @@ -617,25 +619,28 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree LOG.debugFine(msg.toString()); } return appr; - } else { + } + else { a = a - 1; } - } else { - if (marked.contains(a + 1)) { + } + else { + if(marked.contains(a + 1)) { m_a = (y_a - y_s) / (x_a - x_s); - if (y_a == y_p) { + if(y_a == y_p) { m_a = 0; } t_a = y_a - m_a * x_a; ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if (msg != null) { + if(msg != null) { msg.append("3 anchor = ").append(a).append(" -- ").append((a + 1)); msg.append(" appr2 ").append(appr); LOG.debugFine(msg.toString()); } return appr; - } else { + } + else { a = a + 1; } } @@ -657,11 +662,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double upp_error = Double.MAX_VALUE; double upp_m = 0.0; double upp_t = 0.0; - for (int i = 1; i < u; i++) { + for(int i = 1; i < u; i++) { double cur_m = (log_kDist[upperHull[i]] - log_kDist[upperHull[i - 1]]) / (log_k[upperHull[i]] - log_k[upperHull[i - 1]]); double cur_t = log_kDist[upperHull[i]] - cur_m * log_k[upperHull[i]]; double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t); - if (cur_error < upp_error) { + if(cur_error < upp_error) { upp_error = cur_error; upp_m = cur_m; upp_t = cur_t; @@ -669,13 +674,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } // linear search on all points of the upper convex hull boolean is_left = true; // NEEDED FOR PROOF CHECK - for (int i = 0; i < u; i++) { + for(int i = 0; i < u; i++) { double cur_m = optimize(k_0, settings.k_max, sum_log_k, sum_log_k2, log_k[upperHull[i]], log_kDist[upperHull[i]], sum_log_k_kDist, sum_log_kDist); double cur_t = log_kDist[upperHull[i]] - cur_m * log_k[upperHull[i]]; // only valid if both neighboring points are underneath y=mx+t - if ((i == 0 || log_kDist[upperHull[i - 1]] <= log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && (i == u - 1 || log_kDist[upperHull[i + 1]] <= log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) { + if((i == 0 || log_kDist[upperHull[i - 1]] <= log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && (i == u - 1 || log_kDist[upperHull[i + 1]] <= log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) { double cur_error = ssqerr(k_0, settings.k_max, log_k, log_kDist, cur_m, cur_t); - if (cur_error < upp_error) { + if(cur_error < upp_error) { upp_error = cur_error; upp_m = cur_m; upp_t = cur_t; @@ -683,12 +688,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } // check proof of bisection search - if (!(i > 0 && log_kDist[upperHull[i - 1]] > log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && !is_left) { + if(!(i > 0 && log_kDist[upperHull[i - 1]] > log_kDist[upperHull[i]] - cur_m * (log_k[upperHull[i]] - log_k[upperHull[i - 1]])) && !is_left) { // warning("ERROR upper: The bisection search will not work properly !" // + // "\n" + Util.format(log_kDist)); } - if (!(i < u - 1 && log_kDist[upperHull[i + 1]] > log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) { + if(!(i < u - 1 && log_kDist[upperHull[i + 1]] > log_kDist[upperHull[i]] + cur_m * (log_k[upperHull[i + 1]] - log_k[upperHull[i]]))) { is_left = false; } } @@ -703,7 +708,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new leaf node */ @Override - protected MkCoPTreeNode<O, D> createNewLeafNode() { + protected MkCoPTreeNode<O> createNewLeafNode() { return new MkCoPTreeNode<>(leafCapacity, true); } @@ -713,7 +718,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new directory node */ @Override - protected MkCoPTreeNode<O, D> createNewDirectoryNode() { + protected MkCoPTreeNode<O> createNewDirectoryNode() { return new MkCoPTreeNode<>(dirCapacity, false); } @@ -726,7 +731,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * the routing object of the parent node */ @Override - protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O, D> node, DBID routingObjectID, double parentDistance) { + protected MkCoPEntry createNewDirectoryEntry(MkCoPTreeNode<O> node, DBID routingObjectID, double parentDistance) { return new MkCoPDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this), null); // node.conservativeKnnDistanceApproximation(k_max)); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java index 96def76b..1cce0a01 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -36,8 +36,6 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -52,9 +50,8 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type */ -public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree<O, D> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { +public class MkCoPTreeIndex<O> extends MkCoPTree<O> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { /** * Relation indexed */ @@ -67,7 +64,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree * @param pageFile Page file * @param settings Tree settings */ - public MkCoPTreeIndex(Relation<O> relation, PageFile<MkCoPTreeNode<O, D>> pageFile, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> settings) { + public MkCoPTreeIndex(Relation<O> relation, PageFile<MkCoPTreeNode<O>> pageFile, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry> settings) { super(relation, pageFile, settings); this.relation = relation; } @@ -89,7 +86,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree public void initialize() { super.initialize(); List<MkCoPEntry> objs = new ArrayList<>(relation.size()); - for (DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) { + for(DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); // FIXME: expensive final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, Double.NaN)); @@ -97,72 +94,66 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree insertAll(objs); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> KNNQuery<O, S> getKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index - if (distanceQuery.getRelation() != relation) { + if(distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); - if (!this.getDistanceFunction().equals(distanceFunction)) { - if (getLogger().isDebugging()) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); + if(!this.getDistanceFunction().equals(distanceFunction)) { + if(getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); } return null; } // Bulk is not yet supported - for (Object hint : hints) { - if (hint == DatabaseQuery.HINT_BULK) { + for(Object hint : hints) { + if(hint == DatabaseQuery.HINT_BULK) { return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (KNNQuery<O, S>) MTreeQueryUtil.getKNNQuery(this, dq, hints); + return MTreeQueryUtil.getKNNQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RangeQuery<O, S> getRangeQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index - if (distanceQuery.getRelation() != relation) { + if(distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); - if (!this.getDistanceFunction().equals(distanceFunction)) { - if (getLogger().isDebugging()) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); + if(!this.getDistanceFunction().equals(distanceFunction)) { + if(getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); } return null; } // Bulk is not yet supported - for (Object hint : hints) { - if (hint == DatabaseQuery.HINT_BULK) { + for(Object hint : hints) { + if(hint == DatabaseQuery.HINT_BULK) { return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RangeQuery<O, S>) MTreeQueryUtil.getRangeQuery(this, dq, hints); + return MTreeQueryUtil.getRangeQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RKNNQuery<O, S> getRKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); - if (!this.getDistanceFunction().equals(distanceFunction)) { - if (getLogger().isDebugging()) { + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); + if(!this.getDistanceFunction().equals(distanceFunction)) { + if(getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); } return null; } // Bulk is not yet supported - for (Object hint : hints) { - if (hint == DatabaseQuery.HINT_BULK) { + for(Object hint : hints) { + if(hint == DatabaseQuery.HINT_BULK) { return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RKNNQuery<O, S>) new MkTreeRKNNQuery<>(this, dq); + return new MkTreeRKNNQuery<>(this, distanceQuery); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java index 79a9c6cc..dcaa7e05 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -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; @@ -36,9 +35,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; * @apiviz.has MkCoPEntry oneway - - contains * * @param <O> object type - * @param <D> distance type */ -class MkCoPTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> { +class MkCoPTreeNode<O> extends AbstractMTreeNode<O, MkCoPTreeNode<O>, MkCoPEntry> { /** * Serial version UID */ @@ -142,7 +140,7 @@ class MkCoPTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode } @Override - public void adjustEntry(MkCoPEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, ?> mTree) { + public void adjustEntry(MkCoPEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, MkCoPTreeNode<O>, MkCoPEntry, ?> mTree) { super.adjustEntry(entry, routingObjectID, parentDistance, mTree); // adjust conservative distance approximation // int k_max = ((MkCoPTree<O,D>) mTree).getK_max(); @@ -150,11 +148,11 @@ class MkCoPTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode } @Override - protected void integrityCheckParameters(MkCoPEntry parentEntry, MkCoPTreeNode<O, D> parent, int index, AbstractMTree<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, ?> mTree) { + protected void integrityCheckParameters(MkCoPEntry parentEntry, MkCoPTreeNode<O> parent, int index, AbstractMTree<O, MkCoPTreeNode<O>, MkCoPEntry, ?> mTree) { super.integrityCheckParameters(parentEntry, parent, index, mTree); // test conservative approximation MkCoPEntry entry = parent.getEntry(index); - int k_max = ((MkCoPTree<O, D>) mTree).getK_max(); + int k_max = ((MkCoPTree<O>) mTree).getK_max(); ApproximationLine approx = conservativeKnnDistanceApproximation(k_max); if(!entry.getConservativeKnnDistanceApproximation().equals(approx)) { String soll = approx.toString(); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java index fa7afbe2..e6b0ab12 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; */ import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -44,9 +43,8 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; * @apiviz.uses MkCoPTreeIndex oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, MkCoPTreeIndex<O, D>, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry>> { +public class MkCopTreeFactory<O> extends AbstractMTreeFactory<O, MkCoPTreeNode<O>, MkCoPEntry, MkCoPTreeIndex<O>, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry>> { /** * Parameter for k */ @@ -58,17 +56,17 @@ public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * @param pageFileFactory Data storage * @param settings Tree settings */ - public MkCopTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> settings) { + public MkCopTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry> settings) { super(pageFileFactory, settings); } @Override - public MkCoPTreeIndex<O, D> instantiate(Relation<O> relation) { - PageFile<MkCoPTreeNode<O, D>> pagefile = makePageFile(getNodeClass()); + public MkCoPTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<MkCoPTreeNode<O>> pagefile = makePageFile(getNodeClass()); return new MkCoPTreeIndex<>(relation, pagefile, settings); } - protected Class<MkCoPTreeNode<O, D>> getNodeClass() { + protected Class<MkCoPTreeNode<O>> getNodeClass() { return ClassGenericsUtil.uglyCastIntoSubclass(MkCoPTreeNode.class); } @@ -78,8 +76,10 @@ public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type */ - public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory.Parameterizer<O, D, MkCoPTreeNode<O, D>, MkCoPEntry, MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry>> { + public static class Parameterizer<O> extends AbstractMTreeFactory.Parameterizer<O, MkCoPTreeNode<O>, MkCoPEntry, MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry>> { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); @@ -91,12 +91,12 @@ public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac } @Override - protected MkCopTreeFactory<O, D> makeInstance() { + protected MkCopTreeFactory<O> makeInstance() { return new MkCopTreeFactory<>(pageFileFactory, settings); } @Override - protected MkTreeSettings<O, D, MkCoPTreeNode<O, D>, MkCoPEntry> makeSettings() { + protected MkTreeSettings<O, MkCoPTreeNode<O>, MkCoPEntry> makeSettings() { return new MkTreeSettings<>(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/package-info.java index c767c565..4adea565 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxDirectoryEntry.java index b3e39ca0..1cd28215 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 @@ -57,7 +57,7 @@ class MkMaxDirectoryEntry extends MTreeDirectoryEntry implements MkMaxEntry { } /** - * Provides a new MkMaxDirectoryEntry with the given parameters. + * Constructor. * * @param objectID the id of the routing object * @param parentDistance the distance from the routing object of this entry to diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxEntry.java index 9e5133c9..5db6d22c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxLeafEntry.java index d49f18ec..274e6a68 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 @@ -56,7 +56,7 @@ class MkMaxLeafEntry extends MTreeLeafEntry implements MkMaxEntry { } /** - * Provides a new MkMaxLeafEntry with the given parameters. + * Constructor. * * @param objectID the id of the underlying data object * @param parentDistance the distance from the underlying data object to its diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java index e3e4f71f..d099533b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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,20 +30,18 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.logging.Logging; -import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; /** @@ -57,9 +55,8 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; * @apiviz.has MkMaxTreeNode oneway - - contains * * @param <O> the type of DatabaseObject to be stored in the MkMaxTree - * @param <D> the type of Distance used in the MkMaxTree */ -public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnified<O, D, MkMaxTreeNode<O, D>, MkMaxEntry, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry>> { +public class MkMaxTree<O> extends AbstractMkTreeUnified<O, MkMaxTreeNode<O>, MkMaxEntry, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry>> { /** * The logger for this class. */ @@ -72,7 +69,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param pagefile Page file * @param settings Tree settings */ - public MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry> settings) { + public MkMaxTree(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry> settings) { super(relation, pagefile, settings); } @@ -83,13 +80,13 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * in a second step. */ @Override - public DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k) { + public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k) { if (k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be equal or less than " + "parameter k of the MkMax-Tree!"); } // get the candidates - GenericDistanceDBIDList<D> candidates = new GenericDistanceDBIDList<>(); + ModifiableDoubleDBIDList candidates = DBIDUtil.newDistanceDBIDList(); doReverseKNNQuery(id, getRoot(), null, candidates); if (k == this.getKmax()) { @@ -105,15 +102,15 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree for (DBIDIter candidate = candidates.iter(); candidate.valid(); candidate.advance()) { candidateIDs.add(candidate); } - Map<DBID, KNNList<D>> knnLists = batchNN(getRoot(), candidateIDs, k); + Map<DBID, KNNList> knnLists = batchNN(getRoot(), candidateIDs, k); - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); for (DBIDIter iter = candidateIDs.iter(); iter.valid(); iter.advance()) { DBID cid = DBIDUtil.deref(iter); - KNNList<D> cands = knnLists.get(cid); - for (DistanceDBIDListIter<D> iter2 = cands.iter(); iter2.valid(); iter2.advance()) { + KNNList cands = knnLists.get(cid); + for (DoubleDBIDListIter iter2 = cands.iter(); iter2.valid(); iter2.advance()) { if (DBIDUtil.equal(id, iter2)) { - result.add(iter2.getDistance(), cid); + result.add(iter2.doubleValue(), cid); break; } } @@ -132,7 +129,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree */ @Override protected void preInsert(MkMaxEntry entry) { - KNNHeap<D> knns_o = DBIDUtil.newHeap(getDistanceFactory(), getKmax()); + KNNHeap knns_o = DBIDUtil.newHeap(getKmax()); preInsert(entry, getRootEntry(), knns_o); } @@ -140,13 +137,13 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * Adjusts the knn distance in the subtree of the specified root entry. */ @Override - protected void kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID, KNNList<D>> knnLists) { - MkMaxTreeNode<O, D> node = getNode(entry); + protected void kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID, KNNList> knnLists) { + MkMaxTreeNode<O> node = getNode(entry); double knnDist_node = 0.; if (node.isLeaf()) { for (int i = 0; i < node.getNumEntries(); i++) { MkMaxEntry leafEntry = node.getEntry(i); - leafEntry.setKnnDistance(knnLists.get(leafEntry.getRoutingObjectID()).getKNNDistance().doubleValue()); + leafEntry.setKnnDistance(knnLists.get(leafEntry.getRoutingObjectID()).getKNNDistance()); knnDist_node = Math.max(knnDist_node, leafEntry.getKnnDistance()); } } else { @@ -170,13 +167,13 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param node_entry the entry representing the node * @param result the list for the query result */ - private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O, D> node, MkMaxEntry node_entry, ModifiableDistanceDBIDList<D> result) { + private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O> node, MkMaxEntry node_entry, ModifiableDoubleDBIDList result) { // data node if (node.isLeaf()) { for (int i = 0; i < node.getNumEntries(); i++) { MkMaxEntry entry = node.getEntry(i); - D distance = distance(entry.getRoutingObjectID(), q); - if (distance.doubleValue() <= entry.getKnnDistance()) { + double distance = distance(entry.getRoutingObjectID(), q); + if (distance <= entry.getKnnDistance()) { result.add(distance, entry.getRoutingObjectID()); } } @@ -188,11 +185,11 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree MkMaxEntry entry = node.getEntry(i); double node_knnDist = node_entry != null ? node_entry.getKnnDistance() : Double.POSITIVE_INFINITY; - double distance = distance(entry.getRoutingObjectID(), q).doubleValue(); + double distance = distance(entry.getRoutingObjectID(), q); double minDist = (entry.getCoveringRadius() > distance) ? 0.0 : distance - entry.getCoveringRadius(); if (minDist <= node_knnDist) { - MkMaxTreeNode<O, D> childNode = getNode(entry); + MkMaxTreeNode<O> childNode = getNode(entry); doReverseKNNQuery(q, childNode, entry, result); } } @@ -206,39 +203,39 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param nodeEntry the entry representing the root of the current subtree * @param knns_q the knns of q */ - private void preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap<D> knns_q) { + private void preInsert(MkMaxEntry q, MkMaxEntry nodeEntry, KNNHeap knns_q) { if (LOG.isDebugging()) { LOG.debugFine("preInsert " + q + " - " + nodeEntry + "\n"); } - double knnDist_q = knns_q.getKNNDistance().doubleValue(); - MkMaxTreeNode<O, D> node = getNode(nodeEntry); + double knnDist_q = knns_q.getKNNDistance(); + MkMaxTreeNode<O> node = getNode(nodeEntry); double knnDist_node = 0.; // leaf node if (node.isLeaf()) { for (int i = 0; i < node.getNumEntries(); i++) { MkMaxEntry p = node.getEntry(i); - D dist_pq = distance(p.getRoutingObjectID(), q.getRoutingObjectID()); + double dist_pq = distance(p.getRoutingObjectID(), q.getRoutingObjectID()); // p is nearer to q than the farthest kNN-candidate of q // ==> p becomes a knn-candidate - if (dist_pq.doubleValue() <= knnDist_q) { + if (dist_pq <= knnDist_q) { knns_q.insert(dist_pq, p.getRoutingObjectID()); if (knns_q.size() >= getKmax()) { - knnDist_q = knns_q.getKNNDistance().doubleValue(); + knnDist_q = knns_q.getKNNDistance(); q.setKnnDistance(knnDist_q); } } // p is nearer to q than to its farthest knn-candidate // q becomes knn of p - if (dist_pq.doubleValue() <= p.getKnnDistance()) { - KNNList<D> knns_p = knnq.getKNNForDBID(p.getRoutingObjectID(), getKmax() - 1); + if (dist_pq <= p.getKnnDistance()) { + KNNList knns_p = knnq.getKNNForDBID(p.getRoutingObjectID(), getKmax() - 1); if (knns_p.size() + 1 < getKmax()) { p.setKnnDistance(Double.NaN); } else { - double knnDist_p = Math.max(dist_pq.doubleValue(), knns_p.getKNNDistance().doubleValue()); + double knnDist_p = Math.max(dist_pq, knns_p.getKNNDistance()); p.setKnnDistance(knnDist_p); } } @@ -254,7 +251,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree if (distEntry.second < entry_knnDist || distEntry.second < knnDist_q) { preInsert(q, dirEntry, knns_q); - knnDist_q = knns_q.getKNNDistance().doubleValue(); + knnDist_q = knns_q.getKNNDistance(); } knnDist_node = Math.max(knnDist_node, dirEntry.getKnnDistance()); } @@ -305,7 +302,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new MkMaxTreeNode which is a leaf node */ @Override - protected MkMaxTreeNode<O, D> createNewLeafNode() { + protected MkMaxTreeNode<O> createNewLeafNode() { return new MkMaxTreeNode<>(leafCapacity, true); } @@ -313,7 +310,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new MkMaxTreeNode which is a directory node */ @Override - protected MkMaxTreeNode<O, D> createNewDirectoryNode() { + protected MkMaxTreeNode<O> createNewDirectoryNode() { return new MkMaxTreeNode<>(dirCapacity, false); } @@ -321,7 +318,7 @@ public class MkMaxTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new MkMaxDirectoryEntry representing the specified node */ @Override - protected MkMaxEntry createNewDirectoryEntry(MkMaxTreeNode<O, D> node, DBID routingObjectID, double parentDistance) { + protected MkMaxEntry createNewDirectoryEntry(MkMaxTreeNode<O> node, DBID routingObjectID, double parentDistance) { return new MkMaxDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this), node.kNNDistance()); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeFactory.java index a03006f4..0838e6b6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; */ import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnifiedFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -40,26 +39,25 @@ import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; * @apiviz.uses MkMaxTreeIndex oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public class MkMaxTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnifiedFactory<O, D, MkMaxTreeNode<O, D>, MkMaxEntry, MkMaxTreeIndex<O, D>, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry>> { +public class MkMaxTreeFactory<O> extends AbstractMkTreeUnifiedFactory<O, MkMaxTreeNode<O>, MkMaxEntry, MkMaxTreeIndex<O>, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry>> { /** * Constructor. * * @param pageFileFactory Data storage * @param settings Tree settings */ - public MkMaxTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry> settings) { + public MkMaxTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry> settings) { super(pageFileFactory, settings); } @Override - public MkMaxTreeIndex<O, D> instantiate(Relation<O> relation) { - PageFile<MkMaxTreeNode<O, D>> pagefile = makePageFile(getNodeClass()); + public MkMaxTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<MkMaxTreeNode<O>> pagefile = makePageFile(getNodeClass()); return new MkMaxTreeIndex<>(relation, pagefile, settings); } - protected Class<MkMaxTreeNode<O, D>> getNodeClass() { + protected Class<MkMaxTreeNode<O>> getNodeClass() { return ClassGenericsUtil.uglyCastIntoSubclass(MkMaxTreeNode.class); } @@ -69,15 +67,17 @@ public class MkMaxTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type */ - public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnifiedFactory.Parameterizer<O, D, MkMaxTreeNode<O, D>, MkMaxEntry, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry>> { + public static class Parameterizer<O> extends AbstractMkTreeUnifiedFactory.Parameterizer<O, MkMaxTreeNode<O>, MkMaxEntry, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry>> { @Override - protected MkMaxTreeFactory<O, D> makeInstance() { + protected MkMaxTreeFactory<O> makeInstance() { return new MkMaxTreeFactory<>(pageFileFactory, settings); } @Override - protected MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry> makeSettings() { + protected MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry> makeSettings() { return new MkTreeSettings<>(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java index 482c86eb..4468e8b3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 @@ -31,7 +31,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; @@ -39,8 +39,6 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; @@ -58,9 +56,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; * @author Elke Achtert * * @param <O> Object type - * @param <D> Distance type */ -public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree<O, D> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O>, DynamicIndex { +public class MkMaxTreeIndex<O> extends MkMaxTree<O> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O>, DynamicIndex { /** * Relation indexed. */ @@ -73,7 +70,7 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree * @param pagefile Page file * @param settings Tree settings */ - public MkMaxTreeIndex(Relation<O> relation, PageFile<MkMaxTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkMaxTreeNode<O, D>, MkMaxEntry> settings) { + public MkMaxTreeIndex(Relation<O> relation, PageFile<MkMaxTreeNode<O>> pagefile, MkTreeSettings<O, MkMaxTreeNode<O>, MkMaxEntry> settings) { super(relation, pagefile, settings); this.relation = relation; } @@ -82,8 +79,8 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree * @return a new MkMaxLeafEntry representing the specified data object */ protected MkMaxLeafEntry createNewLeafEntry(DBID id, O object, double parentDistance) { - KNNList<D> knns = knnq.getKNNForObject(object, getKmax() - 1); - double knnDistance = knns.getKNNDistance().doubleValue(); + KNNList knns = knnq.getKNNForObject(object, getKmax() - 1); + double knnDistance = knns.getKNNDistance(); return new MkMaxLeafEntry(id, parentDistance, knnDistance); } @@ -133,14 +130,13 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree throw new NotImplementedException(ExceptionMessages.UNSUPPORTED_NOT_YET); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> KNNQuery<O, S> getKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -153,18 +149,16 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (KNNQuery<O, S>) MTreeQueryUtil.getKNNQuery(this, dq, hints); + return MTreeQueryUtil.getKNNQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RangeQuery<O, S> getRangeQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -177,14 +171,12 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RangeQuery<O, S>) MTreeQueryUtil.getRangeQuery(this, dq); + return MTreeQueryUtil.getRangeQuery(this, distanceQuery); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RKNNQuery<O, S> getRKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -197,8 +189,7 @@ public class MkMaxTreeIndex<O, D extends NumberDistance<D, ?>> extends MkMaxTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RKNNQuery<O, S>) new MkTreeRKNNQuery<>(this, dq); + return new MkTreeRKNNQuery<>(this, distanceQuery); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeNode.java index 84c8bdc4..0f9588aa 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -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; @@ -36,9 +35,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; * @apiviz.has MkMaxEntry oneway - - contains * * @param <O> the type of DatabaseObject to be stored in the MkMaxTree - * @param <D> the type of Distance used in the MkMaxTree */ -class MkMaxTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode<O, D, MkMaxTreeNode<O, D>, MkMaxEntry> { +class MkMaxTreeNode<O> extends AbstractMTreeNode<O, MkMaxTreeNode<O>, MkMaxEntry> { /** * Serial version */ @@ -70,7 +68,7 @@ class MkMaxTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode */ protected double kNNDistance() { double knnDist = 0.; - for (int i = 0; i < getNumEntries(); i++) { + for(int i = 0; i < getNumEntries(); i++) { MkMaxEntry entry = getEntry(i); knnDist = Math.max(knnDist, entry.getKnnDistance()); } @@ -83,7 +81,7 @@ class MkMaxTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode * all its entries. */ @Override - public void adjustEntry(MkMaxEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, D, MkMaxTreeNode<O, D>, MkMaxEntry, ?> mTree) { + public void adjustEntry(MkMaxEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, MkMaxTreeNode<O>, MkMaxEntry, ?> mTree) { super.adjustEntry(entry, routingObjectID, parentDistance, mTree); // adjust knn distance entry.setKnnDistance(kNNDistance()); @@ -94,12 +92,12 @@ class MkMaxTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode * node is correctly set. */ @Override - protected void integrityCheckParameters(MkMaxEntry parentEntry, MkMaxTreeNode<O, D> parent, int index, AbstractMTree<O, D, MkMaxTreeNode<O, D>, MkMaxEntry, ?> mTree) { + protected void integrityCheckParameters(MkMaxEntry parentEntry, MkMaxTreeNode<O> parent, int index, AbstractMTree<O, MkMaxTreeNode<O>, MkMaxEntry, ?> mTree) { super.integrityCheckParameters(parentEntry, parent, index, mTree); // test if knn distance is correctly set MkMaxEntry entry = parent.getEntry(index); double knnDistance = kNNDistance(); - if (Math.abs(entry.getKnnDistance() - knnDistance) > 0) { + if(Math.abs(entry.getKnnDistance() - knnDistance) > 0) { throw new RuntimeException("Wrong knnDistance in node " + parent.getPageID() + " at index " + index + " (child " + entry + ")" + "\nsoll: " + knnDistance + ",\n ist: " + entry.getKnnDistance()); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/package-info.java index 7bd90d66..5b368d2e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabDirectoryEntry.java index 9f088448..c8c9e040 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -53,7 +53,7 @@ class MkTabDirectoryEntry extends MTreeDirectoryEntry implements MkTabEntry { } /** - * Provides a new MkMaxDirectoryEntry with the given parameters. + * Constructor. * * @param objectID the id of the routing object * @param parentDistance the distance from the routing object of this entry to @@ -113,7 +113,6 @@ class MkTabDirectoryEntry extends MTreeDirectoryEntry implements MkTabEntry { * cannot be found. */ @Override - @SuppressWarnings("unchecked") public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { super.readExternal(in); int k_max = in.readInt(); @@ -132,7 +131,6 @@ class MkTabDirectoryEntry extends MTreeDirectoryEntry implements MkTabEntry { * knnDistances as this entry. */ @Override - @SuppressWarnings("unchecked") public boolean equals(Object o) { if (this == o) { return true; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java index a741ed5b..f8e48f2a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabLeafEntry.java index 969ba781..122d031e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -53,7 +53,7 @@ class MkTabLeafEntry extends MTreeLeafEntry implements MkTabEntry { } /** - * Provides a new MkMaxLeafEntry with the given parameters. + * Constructor. * * @param objectID the id of the underlying data object * @param parentDistance the distance from the underlying data object to its @@ -115,7 +115,6 @@ class MkTabLeafEntry extends MTreeLeafEntry implements MkTabEntry { * cannot be found. */ @Override - @SuppressWarnings("unchecked") public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { super.readExternal(in); int k_max = in.readInt(); @@ -133,7 +132,6 @@ class MkTabLeafEntry extends MTreeLeafEntry implements MkTabEntry { * and has the same parameter k_max and knnDistances as this entry. */ @Override - @SuppressWarnings("unchecked") public boolean equals(Object o) { if (this == o) { return true; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java index 481392cb..3a377420 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -27,17 +27,17 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.logging.Logging; -import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; /** * MkTabTree is a metrical index structure based on the concepts of the M-Tree @@ -50,9 +50,8 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @apiviz.has MkTabTreeNode oneway - - contains * * @param <O> Object type - * @param <D> Distance type */ -public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnified<O, D, MkTabTreeNode<O, D>, MkTabEntry, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry>> { +public class MkTabTree<O> extends AbstractMkTreeUnified<O, MkTabTreeNode<O>, MkTabEntry, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry>> { /** * The logger for this class. */ @@ -65,7 +64,7 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param pagefile Page file * @param settings Settings */ - public MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry> settings) { + public MkTabTree(Relation<O> relation, PageFile<MkTabTreeNode<O>> pagefile, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry> settings) { super(relation, pagefile, settings); } @@ -88,12 +87,12 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } @Override - public DistanceDBIDList<D> reverseKNNQuery(DBIDRef id, int k) { - if (k > this.getKmax()) { + public DoubleDBIDList reverseKNNQuery(DBIDRef id, int k) { + if(k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MkTab-Tree!"); } - GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); doReverseKNNQuery(k, id, null, getRoot(), result); result.sort(); @@ -106,7 +105,7 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // overhead = index(4), numEntries(4), id(4), isLeaf(0.125) double overhead = 12.125; - if (getPageSize() - overhead < 0) { + if(getPageSize() - overhead < 0) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } @@ -114,11 +113,11 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // coveringRadius + parentDistance + kmax + kmax * knnDistance) + 1 dirCapacity = (int) (getPageSize() - overhead) / (4 + 4 + distanceSize + distanceSize + 4 + getKmax() * distanceSize) + 1; - if (dirCapacity <= 1) { + if(dirCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (dirCapacity < 10) { + if(dirCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } @@ -126,34 +125,35 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // kmax + kmax * knnDistance) + 1 leafCapacity = (int) (getPageSize() - overhead) / (4 + distanceSize + 4 + getKmax() * distanceSize) + 1; - if (leafCapacity <= 1) { + if(leafCapacity <= 1) { throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); } - if (leafCapacity < 10) { + if(leafCapacity < 10) { LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } } @Override - protected void kNNdistanceAdjustment(MkTabEntry entry, Map<DBID, KNNList<D>> knnLists) { - MkTabTreeNode<O, D> node = getNode(entry); + protected void kNNdistanceAdjustment(MkTabEntry entry, Map<DBID, KNNList> knnLists) { + MkTabTreeNode<O> node = getNode(entry); double[] knnDistances_node = initKnnDistanceList(); - if (node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry leafEntry = node.getEntry(i); - KNNList<D> knns = knnLists.get(getPageID(leafEntry)); + KNNList knns = knnLists.get(getPageID(leafEntry)); double[] distances = new double[knns.size()]; int j = 0; - for (DistanceDBIDListIter<D> iter = knns.iter(); iter.valid(); iter.advance(), j++) { - distances[i] = iter.getDistance().doubleValue(); + for(DoubleDBIDListIter iter = knns.iter(); iter.valid(); iter.advance(), j++) { + distances[j] = iter.doubleValue(); } leafEntry.setKnnDistances(distances); // FIXME: save copy knnDistances_node = max(knnDistances_node, leafEntry.getKnnDistances()); } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry dirEntry = node.getEntry(i); kNNdistanceAdjustment(dirEntry, knnLists); // FIXME: save copy @@ -164,7 +164,7 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } @Override - protected MkTabTreeNode<O, D> createNewLeafNode() { + protected MkTabTreeNode<O> createNewLeafNode() { return new MkTabTreeNode<>(leafCapacity, true); } @@ -174,7 +174,7 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a new directory node */ @Override - protected MkTabTreeNode<O, D> createNewDirectoryNode() { + protected MkTabTreeNode<O> createNewDirectoryNode() { return new MkTabTreeNode<>(dirCapacity, false); } @@ -187,7 +187,7 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * the routing object of the parent node */ @Override - protected MkTabEntry createNewDirectoryEntry(MkTabTreeNode<O, D> node, DBID routingObjectID, double parentDistance) { + protected MkTabEntry createNewDirectoryEntry(MkTabTreeNode<O> node, DBID routingObjectID, double parentDistance) { return new MkTabDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this), node.kNNDistances()); } @@ -213,13 +213,13 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param node the root of the subtree * @param result the list holding the query result */ - private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry node_entry, MkTabTreeNode<O, D> node, GenericDistanceDBIDList<D> result) { + private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry node_entry, MkTabTreeNode<O> node, ModifiableDoubleDBIDList result) { // data node - if (node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry entry = node.getEntry(i); - D distance = distance(entry.getRoutingObjectID(), q); - if (distance.doubleValue() <= entry.getKnnDistance(k)) { + double distance = distance(entry.getRoutingObjectID(), q); + if(distance <= entry.getKnnDistance(k)) { result.add(distance, entry.getRoutingObjectID()); } } @@ -227,15 +227,15 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree // directory node else { - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry entry = node.getEntry(i); double node_knnDist = node_entry != null ? node_entry.getKnnDistance(k) : Double.POSITIVE_INFINITY; - double distance = distance(entry.getRoutingObjectID(), q).doubleValue(); + double distance = distance(entry.getRoutingObjectID(), q); double minDist = (entry.getCoveringRadius() > distance) ? 0. : distance - entry.getCoveringRadius(); - if (minDist <= node_knnDist) { - MkTabTreeNode<O, D> childNode = getNode(entry); + if(minDist <= node_knnDist) { + MkTabTreeNode<O> childNode = getNode(entry); doReverseKNNQuery(k, q, entry, childNode, result); } } @@ -252,12 +252,12 @@ public class MkTabTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * in each index */ private double[] max(double[] distances1, double[] distances2) { - if (distances1.length != distances2.length) { + if(distances1.length != distances2.length) { throw new RuntimeException("different lengths!"); } double[] result = new double[distances1.length]; - for (int i = 0; i < distances1.length; i++) { + for(int i = 0; i < distances1.length; i++) { result[i] = Math.max(distances1[i], distances2[i]); } return result; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeFactory.java index 9ede76ad..565735f1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; */ import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnifiedFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.MkTreeSettings; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -40,26 +39,25 @@ import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; * @apiviz.uses MkTabTreeIndex oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ -public class MkTabTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnifiedFactory<O, D, MkTabTreeNode<O, D>, MkTabEntry, MkTabTreeIndex<O, D>, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry>> { +public class MkTabTreeFactory<O> extends AbstractMkTreeUnifiedFactory<O, MkTabTreeNode<O>, MkTabEntry, MkTabTreeIndex<O>, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry>> { /** * Constructor. * * @param pageFileFactory Data storage * @param settings Tree settings */ - public MkTabTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry> settings) { + public MkTabTreeFactory(PageFileFactory<?> pageFileFactory, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry> settings) { super(pageFileFactory, settings); } @Override - public MkTabTreeIndex<O, D> instantiate(Relation<O> relation) { - PageFile<MkTabTreeNode<O, D>> pagefile = makePageFile(getNodeClass()); + public MkTabTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<MkTabTreeNode<O>> pagefile = makePageFile(getNodeClass()); return new MkTabTreeIndex<>(relation, pagefile, settings); } - protected Class<MkTabTreeNode<O, D>> getNodeClass() { + protected Class<MkTabTreeNode<O>> getNodeClass() { return ClassGenericsUtil.uglyCastIntoSubclass(MkTabTreeNode.class); } @@ -70,14 +68,14 @@ public class MkTabTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac * * @apiviz.exclude */ - public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractMkTreeUnifiedFactory.Parameterizer<O, D, MkTabTreeNode<O, D>, MkTabEntry, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry>> { + public static class Parameterizer<O> extends AbstractMkTreeUnifiedFactory.Parameterizer<O, MkTabTreeNode<O>, MkTabEntry, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry>> { @Override - protected MkTabTreeFactory<O, D> makeInstance() { + protected MkTabTreeFactory<O> makeInstance() { return new MkTabTreeFactory<>(pageFileFactory, settings); } @Override - protected MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry> makeSettings() { + protected MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry> makeSettings() { return new MkTreeSettings<>(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java index 150f03e8..713514ff 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -29,8 +29,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; @@ -38,8 +38,6 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -54,9 +52,8 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type */ -public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree<O, D> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { +public class MkTabTreeIndex<O> extends MkTabTree<O> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { /** * The relation indexed. */ @@ -69,7 +66,7 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree * @param pagefile Page file * @param settings Tree settings */ - public MkTabTreeIndex(Relation<O> relation, PageFile<MkTabTreeNode<O, D>> pagefile, MkTreeSettings<O, D, MkTabTreeNode<O, D>, MkTabEntry> settings) { + public MkTabTreeIndex(Relation<O> relation, PageFile<MkTabTreeNode<O>> pagefile, MkTreeSettings<O, MkTabTreeNode<O>, MkTabEntry> settings) { super(relation, pagefile, settings); this.relation = relation; } @@ -93,11 +90,11 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree * @return the knn distance of the object with the specified id */ private double[] knnDistances(O object) { - KNNList<D> knns = knnq.getKNNForObject(object, getKmax() - 1); + KNNList knns = knnq.getKNNForObject(object, getKmax() - 1); double[] distances = new double[getKmax()]; int i = 0; - for (DistanceDBIDListIter<D> iter = knns.iter(); iter.valid() && i < getKmax(); iter.advance(), i++) { - distances[i] = iter.getDistance().doubleValue(); + for (DoubleDBIDListIter iter = knns.iter(); iter.valid() && i < getKmax(); iter.advance(), i++) { + distances[i] = iter.doubleValue(); } return distances; } @@ -114,14 +111,13 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree insertAll(objs); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> KNNQuery<O, S> getKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -134,18 +130,16 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (KNNQuery<O, S>) MTreeQueryUtil.getKNNQuery(this, dq, hints); + return MTreeQueryUtil.getKNNQuery(this, distanceQuery, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RangeQuery<O, S> getRangeQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -158,14 +152,12 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RangeQuery<O, S>) MTreeQueryUtil.getRangeQuery(this, dq); + return MTreeQueryUtil.getRangeQuery(this, distanceQuery); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RKNNQuery<O, S> getRKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -178,8 +170,7 @@ public class MkTabTreeIndex<O, D extends NumberDistance<D, ?>> extends MkTabTree return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RKNNQuery<O, S>) new MkTreeRKNNQuery<>(this, dq); + return new MkTreeRKNNQuery<>(this, distanceQuery); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeNode.java index 1942a78b..913a3261 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -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; @@ -36,9 +35,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; * @apiviz.has MkTabEntry oneway - - contains * * @param <O> object type - * @param <D> distance type */ -class MkTabTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode<O, D, MkTabTreeNode<O, D>, MkTabEntry> { +class MkTabTreeNode<O> extends AbstractMTreeNode<O, MkTabTreeNode<O>, MkTabEntry> { private static final long serialVersionUID = 2; /** @@ -81,7 +79,7 @@ class MkTabTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode } @Override - public void adjustEntry(MkTabEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, D, MkTabTreeNode<O, D>, MkTabEntry, ?> mTree) { + public void adjustEntry(MkTabEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, MkTabTreeNode<O>, MkTabEntry, ?> mTree) { super.adjustEntry(entry, routingObjectID, parentDistance, mTree); // adjust knn distances entry.setKnnDistances(kNNDistances()); @@ -96,7 +94,7 @@ class MkTabTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode * @param mTree the underlying M-Tree */ @Override - protected void integrityCheckParameters(MkTabEntry parentEntry, MkTabTreeNode<O, D> parent, int index, AbstractMTree<O, D, MkTabTreeNode<O, D>, MkTabEntry, ?> mTree) { + protected void integrityCheckParameters(MkTabEntry parentEntry, MkTabTreeNode<O> parent, int index, AbstractMTree<O, MkTabTreeNode<O>, MkTabEntry, ?> mTree) { super.integrityCheckParameters(parentEntry, parent, index, mTree); // test knn distances MkTabEntry entry = parent.getEntry(index); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/package-info.java index ed3e24d3..8b81f375 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/package-info.java index 13b23e16..976b3436 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/package-info.java @@ -7,7 +7,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java index 1b3d1481..78a8b95e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -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.MTreeDirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; @@ -53,12 +52,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title; * @apiviz.has MTreeNode oneway - - contains * * @param <O> the type of DatabaseObject to be stored in the metrical index - * @param <D> the type of Distance used in the metrical index */ @Title("M-Tree") @Description("Efficient Access Method for Similarity Search in Metric Spaces") @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -abstract public class MTree<O, D extends NumberDistance<D, ?>> extends AbstractMTree<O, D, MTreeNode<O, D>, MTreeEntry, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry>> { +abstract public class MTree<O> extends AbstractMTree<O, MTreeNode<O>, MTreeEntry, MTreeSettings<O, MTreeNode<O>, MTreeEntry>> { /** * The logger for this class. */ @@ -70,7 +68,7 @@ abstract public class MTree<O, D extends NumberDistance<D, ?>> extends AbstractM * @param pagefile Page file * @param settings Tree settings */ - public MTree(PageFile<MTreeNode<O, D>> pagefile, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry> settings) { + public MTree(PageFile<MTreeNode<O>> pagefile, MTreeSettings<O, MTreeNode<O>, MTreeEntry> settings) { super(pagefile, settings); } @@ -86,7 +84,7 @@ abstract public class MTree<O, D extends NumberDistance<D, ?>> extends AbstractM * @return a new MTreeDirectoryEntry representing the specified node */ @Override - protected MTreeEntry createNewDirectoryEntry(MTreeNode<O, D> node, DBID routingObjectID, double parentDistance) { + protected MTreeEntry createNewDirectoryEntry(MTreeNode<O> node, DBID routingObjectID, double parentDistance) { return new MTreeDirectoryEntry(routingObjectID, parentDistance, node.getPageID(), node.coveringRadius(routingObjectID, this)); } @@ -103,7 +101,7 @@ abstract public class MTree<O, D extends NumberDistance<D, ?>> extends AbstractM * @return a new MTreeNode which is a leaf node */ @Override - protected MTreeNode<O, D> createNewLeafNode() { + protected MTreeNode<O> createNewLeafNode() { return new MTreeNode<>(leafCapacity, true); } @@ -111,7 +109,7 @@ abstract public class MTree<O, D extends NumberDistance<D, ?>> extends AbstractM * @return a new MTreeNode which is a directory node */ @Override - protected MTreeNode<O, D> createNewDirectoryNode() { + protected MTreeNode<O> createNewDirectoryNode() { return new MTreeNode<>(dirCapacity, false); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java index dbc27511..1d6a06a6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; 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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; */ import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeFactory; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeSettings; @@ -42,27 +41,26 @@ import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; * @apiviz.uses MTreeIndex oneway - - «create» * * @param <O> Object type - * @param <D> Distance type */ @Alias({ "mtree", "m" }) -public class MTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory<O, D, MTreeNode<O, D>, MTreeEntry, MTreeIndex<O, D>, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry>> { +public class MTreeFactory<O> extends AbstractMTreeFactory<O, MTreeNode<O>, MTreeEntry, MTreeIndex<O>, MTreeSettings<O, MTreeNode<O>, MTreeEntry>> { /** * Constructor. * * @param pageFileFactory Data storage * @param settings Tree settings */ - public MTreeFactory(PageFileFactory<?> pageFileFactory, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry> settings) { + public MTreeFactory(PageFileFactory<?> pageFileFactory, MTreeSettings<O, MTreeNode<O>, MTreeEntry> settings) { super(pageFileFactory, settings); } @Override - public MTreeIndex<O, D> instantiate(Relation<O> relation) { - PageFile<MTreeNode<O, D>> pagefile = makePageFile(getNodeClass()); + public MTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<MTreeNode<O>> pagefile = makePageFile(getNodeClass()); return new MTreeIndex<>(relation, pagefile, settings); } - protected Class<MTreeNode<O, D>> getNodeClass() { + protected Class<MTreeNode<O>> getNodeClass() { return ClassGenericsUtil.uglyCastIntoSubclass(MTreeNode.class); } @@ -72,15 +70,17 @@ public class MTreeFactory<O, D extends NumberDistance<D, ?>> extends AbstractMTr * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type */ - public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractMTreeFactory.Parameterizer<O, D, MTreeNode<O, D>, MTreeEntry, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry>> { + public static class Parameterizer<O> extends AbstractMTreeFactory.Parameterizer<O, MTreeNode<O>, MTreeEntry, MTreeSettings<O, MTreeNode<O>, MTreeEntry>> { @Override - protected MTreeFactory<O, D> makeInstance() { + protected MTreeFactory<O> makeInstance() { return new MTreeFactory<>(pageFileFactory, settings); } @Override - protected MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry> makeSettings() { + protected MTreeSettings<O, MTreeNode<O>, MTreeEntry> makeSettings() { return new MTreeSettings<>(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java index 32908a1e..e5dd8972 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; 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 @@ -39,8 +39,6 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -48,10 +46,10 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeLeafEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; -import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; /** * Class for using an m-tree as database index. @@ -59,9 +57,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; * @author Erich Schubert * * @param <O> Object type - * @param <D> Distance type */ -public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { +public class MTreeIndex<O> extends MTree<O> implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { /** * The relation indexed. */ @@ -70,7 +67,7 @@ public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> i /** * The distance query. */ - protected DistanceQuery<O, D> distanceQuery; + protected DistanceQuery<O> distanceQuery; /** * Constructor. @@ -79,16 +76,16 @@ public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> i * @param pagefile Page file * @param settings Tree settings */ - public MTreeIndex(Relation<O> relation, PageFile<MTreeNode<O, D>> pagefile, MTreeSettings<O, D, MTreeNode<O, D>, MTreeEntry> settings) { + public MTreeIndex(Relation<O> relation, PageFile<MTreeNode<O>> pagefile, MTreeSettings<O, MTreeNode<O>, MTreeEntry> settings) { super(pagefile, settings); this.relation = relation; this.distanceQuery = getDistanceFunction().instantiate(relation); } @Override - public D distance(DBIDRef id1, DBIDRef id2) { + public double distance(DBIDRef id1, DBIDRef id2) { if (id1 == null || id2 == null) { - return getDistanceFactory().undefinedDistance(); + return Double.NaN; } statistics.countDistanceCalculation(); return distanceQuery.distance(id1, id2); @@ -196,14 +193,13 @@ public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> i throw new NotImplementedException(ExceptionMessages.UNSUPPORTED_NOT_YET); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> KNNQuery<O, S> getKNNQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -216,18 +212,17 @@ public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> i return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (KNNQuery<O, S>) MTreeQueryUtil.getKNNQuery(this, dq, hints); + DistanceQuery<O> dq = distanceFunction.instantiate(relation); + return MTreeQueryUtil.getKNNQuery(this, dq, hints); } - @SuppressWarnings("unchecked") @Override - public <S extends Distance<S>> RangeQuery<O, S> getRangeQuery(DistanceQuery<O, S> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if (distanceQuery.getRelation() != relation) { return null; } - DistanceFunction<? super O, D> distanceFunction = (DistanceFunction<? super O, D>) distanceQuery.getDistanceFunction(); + DistanceFunction<? super O> distanceFunction = (DistanceFunction<? super O>) distanceQuery.getDistanceFunction(); if (!this.getDistanceFunction().equals(distanceFunction)) { if (getLogger().isDebugging()) { getLogger().debug("Distance function not supported by index - or 'equals' not implemented right!"); @@ -240,8 +235,8 @@ public class MTreeIndex<O, D extends NumberDistance<D, ?>> extends MTree<O, D> i return null; } } - DistanceQuery<O, D> dq = distanceFunction.instantiate(relation); - return (RangeQuery<O, S>) MTreeQueryUtil.getRangeQuery(this, dq); + DistanceQuery<O> dq = distanceFunction.instantiate(relation); + return MTreeQueryUtil.getRangeQuery(this, dq); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeNode.java index b3aa77fb..61dc7594 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; @@ -32,9 +31,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; * * @author Elke Achtert * @param <O> Object type - * @param <D> Distance type */ -public class MTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode<O, D, MTreeNode<O, D>, MTreeEntry> { +public class MTreeNode<O> extends AbstractMTreeNode<O, MTreeNode<O>, MTreeEntry> { /** * Serial version */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/package-info.java index c10d683b..aec2fd17 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/package-info.java index 03a4a4d6..922a299a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java deleted file mode 100644 index b55b9fd0..00000000 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java +++ /dev/null @@ -1,143 +0,0 @@ -package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2013 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; -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; -import de.lmu.ifi.dbs.elki.index.tree.query.DoubleMTreeDistanceSearchCandidate; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; - -/** - * Instance of a KNN query for a particular spatial index. - * - * @author Erich Schubert - * - * @apiviz.uses AbstractMTree - * - * @param <O> Object type - */ -public class DoubleDistanceMetricalIndexKNNQuery<O> extends AbstractDistanceKNNQuery<O, DoubleDistance> { - /** - * The index to use - */ - protected final AbstractMTree<O, DoubleDistance, ?, ?, ?> index; - - /** - * Distance function - */ - protected PrimitiveDoubleDistanceFunction<? super O> distf; - - /** - * Constructor. - * - * @param index Index to use - * @param distanceQuery Distance query used - * @param distf Distance function - */ - public DoubleDistanceMetricalIndexKNNQuery(AbstractMTree<O, DoubleDistance, ?, ?, ?> index, DistanceQuery<O, DoubleDistance> distanceQuery, PrimitiveDoubleDistanceFunction<? super O> distf) { - super(distanceQuery); - this.index = index; - this.distf = distf; - } - - @Override - public KNNList<DoubleDistance> getKNNForObject(O q, int k) { - if (k < 1) { - throw new IllegalArgumentException("At least one object has to be requested!"); - } - index.statistics.countKNNQuery(); - - DoubleDistanceKNNHeap knnList = DBIDUtil.newDoubleDistanceHeap(k); - double d_k = Double.POSITIVE_INFINITY; - - final ComparableMinHeap<DoubleMTreeDistanceSearchCandidate> pq = new ComparableMinHeap<>(); - - // Push the root node - pq.add(new DoubleMTreeDistanceSearchCandidate(0, index.getRootID(), null, 0)); - - // search in tree - while (!pq.isEmpty()) { - DoubleMTreeDistanceSearchCandidate pqNode = pq.poll(); - DBID id_p = pqNode.routingObjectID; - double d1 = pqNode.routingDistance; - - if (knnList.size() >= k && pqNode.mindist > d_k) { - break; - } - - AbstractMTreeNode<?, DoubleDistance, ?, ?> node = index.getNode(pqNode.nodeID); - - // directory node - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { - final MTreeEntry entry = node.getEntry(i); - final DBID id_i = entry.getRoutingObjectID(); - double or_i = entry.getCoveringRadius(); - double d2 = id_p != null ? entry.getParentDistance() : 0; - double diff = Math.abs(d1 - d2); - - if (diff <= d_k + or_i) { - final O ob_i = relation.get(id_i); - double d3 = distf.doubleDistance(ob_i, q); - index.statistics.countDistanceCalculation(); - double d_min = Math.max(d3 - or_i, 0); - if (d_min <= d_k) { - pq.add(new DoubleMTreeDistanceSearchCandidate(d_min, ((DirectoryEntry) entry).getPageID(), id_i, d3)); - } - } - } - } - // data node - else { - for (int i = 0; i < node.getNumEntries(); i++) { - final MTreeEntry entry = node.getEntry(i); - final DBID id_i = entry.getRoutingObjectID(); - double d2 = id_p != null ? entry.getParentDistance() : 0; - double diff = Math.abs(d1 - d2); - - if (diff <= d_k) { - final O o_i = relation.get(id_i); - double d3 = distf.doubleDistance(o_i, q); - index.statistics.countDistanceCalculation(); - if (d3 <= d_k) { - knnList.insert(d3, id_i); - d_k = knnList.doubleKNNDistance(); - } - } - } - } - } - return knnList.toKNNList(); - } -} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java deleted file mode 100644 index 714498d4..00000000 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java +++ /dev/null @@ -1,137 +0,0 @@ -package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2013 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPairList; -import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; -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; - -/** - * Instance of a range query for a particular spatial index. - * - * @author Erich Schubert - * - * @apiviz.uses AbstractMTree - */ -public class DoubleDistanceMetricalIndexRangeQuery<O> extends AbstractDistanceRangeQuery<O, DoubleDistance> { - /** - * The index to use - */ - protected final AbstractMTree<O, DoubleDistance, ?, ?, ?> index; - - /** - * Distance function - */ - protected PrimitiveDoubleDistanceFunction<? super O> distf; - - /** - * Constructor. - * - * @param index Index to use - * @param distanceQuery Distance query used - * @param distf Distance function - */ - public DoubleDistanceMetricalIndexRangeQuery(AbstractMTree<O, DoubleDistance, ?, ?, ?> index, DistanceQuery<O, DoubleDistance> distanceQuery, PrimitiveDoubleDistanceFunction<? super O> distf) { - super(distanceQuery); - this.index = index; - this.distf = distf; - } - - /** - * Performs a range query on the specified subtree. It recursively traverses - * all paths from the specified node, which cannot be excluded from leading to - * qualifying objects. - * - * @param id_p the routing object of the specified node - * @param node the root of the subtree to be traversed - * @param q the query object - * @param r_q the query range - * @param result the list holding the query results - */ - private void doRangeQuery(DBID id_p, AbstractMTreeNode<O, DoubleDistance, ?, ?> node, O q, double r_q, ModifiableDoubleDistanceDBIDList result) { - final O o_p = id_p != null ? relation.get(id_p) : null; - double d1 = 0.; - if (id_p != null) { - d1 = distf.doubleDistance(o_p, q); - index.statistics.countDistanceCalculation(); - } - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { - MTreeEntry entry = node.getEntry(i); - - double r_or = entry.getCoveringRadius(); - double d2 = id_p != null ? entry.getParentDistance() : 0; - double diff = Math.abs(d1 - d2); - - double sum = r_q + r_or; - - if (diff <= sum) { - DBID id_r = entry.getRoutingObjectID(); - double d3 = distf.doubleDistance(relation.get(id_r), q); - index.statistics.countDistanceCalculation(); - if (d3 <= sum) { - AbstractMTreeNode<O, DoubleDistance, ?, ?> child = index.getNode(((DirectoryEntry) entry).getPageID()); - doRangeQuery(id_r, child, q, r_q, result); - } - } - } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { - MTreeEntry entry = node.getEntry(i); - - double d2 = id_p != null ? entry.getParentDistance() : 0; - double diff = Math.abs(d1 - d2); - - if (diff <= r_q) { - DBID id_j = entry.getRoutingObjectID(); - O o_j = relation.get(id_j); - double d3 = distf.doubleDistance(o_j, q); - index.statistics.countDistanceCalculation(); - if (d3 <= r_q) { - result.add(d3, id_j); - } - } - } - } - } - - @Override - public DistanceDBIDList<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { - final DoubleDistanceDBIDPairList result = new DoubleDistanceDBIDPairList(); - - doRangeQuery(null, index.getRoot(), obj, range.doubleValue(), result); - index.statistics.countRangeQuery(); - result.sort(); - return result; - } -} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java index cc27b383..8bd0ceb0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java @@ -3,17 +3,13 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; /* 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 @@ -43,23 +39,12 @@ public final class MTreeQueryUtil { * possible. * * @param <O> Object type - * @param <D> Distance type * @param tree Tree to query * @param distanceQuery distance query * @param hints Optimizer hints * @return Query object */ - @SuppressWarnings({ "cast", "unchecked" }) - public static <O, D extends NumberDistance<D, ?>> KNNQuery<O, D> getKNNQuery(AbstractMTree<O, D, ?, ?, ?> tree, DistanceQuery<O, D> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); - // Can we use an optimized query? - if (df instanceof PrimitiveDoubleDistanceFunction) { - PrimitiveDoubleDistanceFunction<? super O> dfc = (PrimitiveDoubleDistanceFunction<? super O>) df; - AbstractMTree<O, DoubleDistance, ?, ?, ?> treec = (AbstractMTree<O, DoubleDistance, ?, ?, ?>) tree; - DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) distanceQuery; - KNNQuery<O, ?> q = new DoubleDistanceMetricalIndexKNNQuery<>(treec, dqc, dfc); - return (KNNQuery<O, D>) q; - } + public static <O> KNNQuery<O> getKNNQuery(AbstractMTree<O, ?, ?, ?> tree, DistanceQuery<O> distanceQuery, Object... hints) { return new MetricalIndexKNNQuery<>(tree, distanceQuery); } @@ -68,23 +53,12 @@ public final class MTreeQueryUtil { * possible. * * @param <O> Object type - * @param <D> Distance type * @param tree Tree to query * @param distanceQuery distance query * @param hints Optimizer hints * @return Query object */ - @SuppressWarnings({ "cast", "unchecked" }) - public static <O, D extends NumberDistance<D, ?>> RangeQuery<O, D> getRangeQuery(AbstractMTree<O, D, ?, ?, ?> tree, DistanceQuery<O, D> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); - // Can we use an optimized query? - if (df instanceof PrimitiveDoubleDistanceFunction) { - PrimitiveDoubleDistanceFunction<? super O> dfc = (PrimitiveDoubleDistanceFunction<? super O>) df; - AbstractMTree<O, DoubleDistance, ?, ?, ?> treec = (AbstractMTree<O, DoubleDistance, ?, ?, ?>) tree; - DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) distanceQuery; - RangeQuery<O, ?> q = new DoubleDistanceMetricalIndexRangeQuery<>(treec, dqc, dfc); - return (RangeQuery<O, D>) q; - } + public static <O> RangeQuery<O> getRangeQuery(AbstractMTree<O, ?, ?, ?> tree, DistanceQuery<O> distanceQuery, Object... hints) { return new MetricalIndexRangeQuery<>(tree, distanceQuery); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java index f21bac82..d839bed3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; 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 @@ -25,11 +25,10 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; @@ -43,15 +42,15 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; * @author Erich Schubert * * @apiviz.uses AbstractMTree + * @apiviz.uses DoubleMTreeDistanceSearchCandidate * * @param <O> Object type - * @param <D> Distance type */ -public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends AbstractDistanceKNNQuery<O, D> { +public class MetricalIndexKNNQuery<O> extends AbstractDistanceKNNQuery<O> { /** * The index to use */ - protected final AbstractMTree<O, D, ?, ?, ?> index; + protected final AbstractMTree<O, ?, ?, ?> index; /** * Constructor. @@ -59,41 +58,41 @@ public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends Ab * @param index Index to use * @param distanceQuery Distance query used */ - public MetricalIndexKNNQuery(AbstractMTree<O, D, ?, ?, ?> index, DistanceQuery<O, D> distanceQuery) { + public MetricalIndexKNNQuery(AbstractMTree<O, ?, ?, ?> index, DistanceQuery<O> distanceQuery) { super(distanceQuery); this.index = index; } @Override - public KNNList<D> getKNNForObject(O q, int k) { - if (k < 1) { + public KNNList getKNNForObject(O q, int k) { + if(k < 1) { throw new IllegalArgumentException("At least one object has to be requested!"); } index.statistics.countKNNQuery(); - KNNHeap<D> knnList = DBIDUtil.newHeap(distanceQuery.getDistanceFactory(), k); - D d_k = knnList.getKNNDistance(); + KNNHeap knnList = DBIDUtil.newHeap(k); + double d_k = Double.POSITIVE_INFINITY; final ComparableMinHeap<DoubleMTreeDistanceSearchCandidate> pq = new ComparableMinHeap<>(); - // push root + // Push the root node pq.add(new DoubleMTreeDistanceSearchCandidate(0., index.getRootID(), null, 0.)); // search in tree - while (!pq.isEmpty()) { + while(!pq.isEmpty()) { DoubleMTreeDistanceSearchCandidate pqNode = pq.poll(); - if (knnList.size() >= k && pqNode.mindist > d_k.doubleValue()) { + if(knnList.size() >= k && pqNode.mindist > d_k) { break; } - AbstractMTreeNode<?, D, ?, ?> node = index.getNode(pqNode.nodeID); + AbstractMTreeNode<?, ?, ?> node = index.getNode(pqNode.nodeID); DBID id_p = pqNode.routingObjectID; double d1 = pqNode.routingDistance; // directory node - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(!node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MTreeEntry entry = node.getEntry(i); DBID o_r = entry.getRoutingObjectID(); double r_or = entry.getCoveringRadius(); @@ -101,13 +100,13 @@ public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends Ab double diff = Math.abs(d1 - d2); - double sum = d_k.doubleValue() + r_or; + double sum = d_k + r_or; - if (diff <= sum) { - double d3 = distanceQuery.distance(o_r, q).doubleValue(); + if(diff <= sum) { + double d3 = distanceQuery.distance(o_r, q); index.statistics.countDistanceCalculation(); double d_min = Math.max(d3 - r_or, 0.); - if (d_min <= d_k.doubleValue()) { + if(d_min <= d_k) { pq.add(new DoubleMTreeDistanceSearchCandidate(d_min, ((DirectoryEntry) entry).getPageID(), o_r, d3)); } } @@ -115,7 +114,7 @@ public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends Ab } // data node else { - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { MTreeEntry entry = node.getEntry(i); DBID o_j = entry.getRoutingObjectID(); @@ -123,10 +122,10 @@ public class MetricalIndexKNNQuery<O, D extends NumberDistance<D, ?>> extends Ab double diff = Math.abs(d1 - d2); - if (diff <= d_k.doubleValue()) { - D d3 = distanceQuery.distance(o_j, q); + if(diff <= d_k) { + double d3 = distanceQuery.distance(o_j, q); index.statistics.countDistanceCalculation(); - if (d3.compareTo(d_k) <= 0) { + if(d3 <= d_k) { knnList.insert(d3, o_j); d_k = knnList.getKNNDistance(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java index fedf8ddb..b992977c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; 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 @@ -24,11 +24,11 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; @@ -40,12 +40,14 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; * @author Erich Schubert * * @apiviz.uses AbstractMTree + * + * @param <O> Object type */ -public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends AbstractDistanceRangeQuery<O, D> { +public class MetricalIndexRangeQuery<O> extends AbstractDistanceRangeQuery<O> { /** * The index to use */ - protected final AbstractMTree<O, D, ?, ?, ?> index; + protected final AbstractMTree<O, ?, ?, ?> index; /** * Constructor. @@ -53,7 +55,7 @@ public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends * @param index Index to use * @param distanceQuery Distance query used */ - public MetricalIndexRangeQuery(AbstractMTree<O, D, ?, ?, ?> index, DistanceQuery<O, D> distanceQuery) { + public MetricalIndexRangeQuery(AbstractMTree<O, ?, ?, ?> index, DistanceQuery<O> distanceQuery) { super(distanceQuery); this.index = index; } @@ -65,18 +67,18 @@ public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends * * @param o_p the routing object of the specified node * @param node the root of the subtree to be traversed - * @param q the id of the query object + * @param q the query object * @param r_q the query range * @param result the list holding the query results */ - private void doRangeQuery(DBID o_p, AbstractMTreeNode<O, D, ?, ?> node, O q, D r_q, GenericDistanceDBIDList<D> result) { + private void doRangeQuery(DBID o_p, AbstractMTreeNode<O, ?, ?> node, O q, double r_q, ModifiableDoubleDBIDList result) { double d1 = 0.; - if (o_p != null) { - d1 = distanceQuery.distance(o_p, q).doubleValue(); + if(o_p != null) { + d1 = distanceQuery.distance(o_p, q); index.statistics.countDistanceCalculation(); } - if (!node.isLeaf()) { - for (int i = 0; i < node.getNumEntries(); i++) { + if(!node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { MTreeEntry entry = node.getEntry(i); DBID o_r = entry.getRoutingObjectID(); @@ -84,19 +86,20 @@ public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends double d2 = o_p != null ? entry.getParentDistance() : 0.; double diff = Math.abs(d1 - d2); - double sum = r_q.doubleValue() + r_or; + double sum = r_q + r_or; - if (diff <= sum) { - D d3 = distanceQuery.distance(o_r, q); + if(diff <= sum) { + double d3 = distanceQuery.distance(o_r, q); index.statistics.countDistanceCalculation(); - if (d3.doubleValue() <= sum) { - AbstractMTreeNode<O, D, ?, ?> child = index.getNode(((DirectoryEntry) entry).getPageID()); + if(d3 <= sum) { + AbstractMTreeNode<O, ?, ?> child = index.getNode(((DirectoryEntry) entry).getPageID()); doRangeQuery(o_r, child, q, r_q, result); } } } - } else { - for (int i = 0; i < node.getNumEntries(); i++) { + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { MTreeEntry entry = node.getEntry(i); DBID o_j = entry.getRoutingObjectID(); @@ -104,10 +107,10 @@ public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends double diff = Math.abs(d1 - d2); - if (diff <= r_q.doubleValue()) { - D d3 = distanceQuery.distance(o_j, q); + if(diff <= r_q) { + double d3 = distanceQuery.distance(o_j, q); index.statistics.countDistanceCalculation(); - if (d3.compareTo(r_q) <= 0) { + if(d3 <= r_q) { result.add(d3, o_j); } } @@ -116,8 +119,8 @@ public class MetricalIndexRangeQuery<O, D extends NumberDistance<D, ?>> extends } @Override - public DistanceDBIDList<D> getRangeForObject(O obj, D range) { - final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + public DoubleDBIDList getRangeForObject(O obj, double range) { + final ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); doRangeQuery(null, index.getRoot(), obj, range, result); index.statistics.countRangeQuery(); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java index c8cec69f..a00e44a9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; 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 @@ -27,10 +27,9 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.AbstractRKNNQuery; -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; @@ -43,11 +42,11 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; * * @apiviz.uses AbstractMkTree */ -public class MkTreeRKNNQuery<O, D extends NumberDistance<D, ?>> extends AbstractRKNNQuery<O, D> { +public class MkTreeRKNNQuery<O> extends AbstractRKNNQuery<O> { /** * The index to use */ - protected final AbstractMkTree<O, D, ?, ?, ?> index; + protected final AbstractMkTree<O, ?, ?, ?> index; /** * Constructor. @@ -55,23 +54,23 @@ public class MkTreeRKNNQuery<O, D extends NumberDistance<D, ?>> extends Abstract * @param index Index to use * @param distanceQuery Distance query used */ - public MkTreeRKNNQuery(AbstractMkTree<O, D, ?, ?, ?> index, DistanceQuery<O, D> distanceQuery) { + public MkTreeRKNNQuery(AbstractMkTree<O, ?, ?, ?> index, DistanceQuery<O> distanceQuery) { super(distanceQuery); this.index = index; } @Override - public DistanceDBIDList<D> getRKNNForObject(O obj, int k) { + public DoubleDBIDList getRKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @Override - public DistanceDBIDList<D> getRKNNForDBID(DBIDRef id, int k) { + public DoubleDBIDList getRKNNForDBID(DBIDRef id, int k) { return index.reverseKNNQuery(id, k); } @Override - public List<? extends DistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends DoubleDBIDList> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { // TODO: implement throw new NotImplementedException(ExceptionMessages.UNSUPPORTED_NOT_YET); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/package-info.java index a975fdff..5ad2593c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/package-info.java @@ -6,7 +6,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MTreeInsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MTreeInsert.java index 65fc3768..5fff4143 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MTreeInsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MTreeInsert.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert; 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 @@ -22,7 +22,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert; You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; @@ -38,7 +37,7 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; * * @author Erich Schubert */ -public interface MTreeInsert<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> { +public interface MTreeInsert<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> { /** * Choose the subpath to insert into. * @@ -46,5 +45,5 @@ public interface MTreeInsert<O, D extends NumberDistance<D, ?>, N extends Abstra * @param object Object to insert * @return Path to insertion node */ - IndexTreePath<E> choosePath(AbstractMTree<O, D, N, E, ?> tree, E object); + IndexTreePath<E> choosePath(AbstractMTree<O, N, E, ?> tree, E object); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MinimumEnlargementInsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MinimumEnlargementInsert.java index f848f5f4..cb410a8d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MinimumEnlargementInsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/MinimumEnlargementInsert.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert; 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 @@ -22,7 +22,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert; You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; import de.lmu.ifi.dbs.elki.index.tree.TreeIndexPathComponent; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; @@ -44,9 +43,9 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Erich Schubert */ @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -public class MinimumEnlargementInsert<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> implements MTreeInsert<O, D, N, E> { +public class MinimumEnlargementInsert<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> implements MTreeInsert<O, N, E> { @Override - public IndexTreePath<E> choosePath(AbstractMTree<O, D, N, E, ?> tree, E object) { + public IndexTreePath<E> choosePath(AbstractMTree<O, N, E, ?> tree, E object) { return choosePath(tree, object, tree.getRootPath()); } @@ -59,7 +58,7 @@ public class MinimumEnlargementInsert<O, D extends NumberDistance<D, ?>, N exten * @param subtree the subtree to be tested for insertion * @return the path of the appropriate subtree to insert the given object */ - private IndexTreePath<E> choosePath(AbstractMTree<O, D, N, E, ?> tree, E object, IndexTreePath<E> subtree) { + private IndexTreePath<E> choosePath(AbstractMTree<O, N, E, ?> tree, E object, IndexTreePath<E> subtree) { N node = tree.getNode(subtree.getLastPathComponent().getEntry()); // leaf @@ -75,7 +74,7 @@ public class MinimumEnlargementInsert<O, D extends NumberDistance<D, ?>, N exten { bestIdx = 0; bestEntry = node.getEntry(0); - bestDistance = tree.distance(object.getRoutingObjectID(), bestEntry.getRoutingObjectID()).doubleValue(); + bestDistance = tree.distance(object.getRoutingObjectID(), bestEntry.getRoutingObjectID()); if (bestDistance <= bestEntry.getCoveringRadius()) { enlarge = 0.; } else { @@ -86,7 +85,7 @@ public class MinimumEnlargementInsert<O, D extends NumberDistance<D, ?>, N exten // Iterate over remaining for (int i = 1; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); - double distance = tree.distance(object.getRoutingObjectID(), entry.getRoutingObjectID()).doubleValue(); + double distance = tree.distance(object.getRoutingObjectID(), entry.getRoutingObjectID()); if (distance <= entry.getCoveringRadius()) { if (enlarge > 0. || distance < bestDistance) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/package-info.java index 64a85c2d..655611c6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/insert/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/package-info.java index 0d019cf3..61d2d899 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/package-info.java @@ -5,7 +5,7 @@ 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/Assignments.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/Assignments.java index 1079a141..cbf7e3eb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/Assignments.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/Assignments.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 @@ -69,7 +69,7 @@ public class Assignments<E extends MTreeEntry> { private List<DistanceEntry<E>> secondAssignments; /** - * Provides an assignment during a split of an MTree node. + * Constructor. * * @param id1 the first routing object * @param id2 the second routing object diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/DistanceEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/DistanceEntry.java index 642e5a63..4df9aa59 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/DistanceEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/DistanceEntry.java @@ -6,7 +6,7 @@ import de.lmu.ifi.dbs.elki.index.tree.Entry; 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 diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MLBDistSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MLBDistSplit.java index d294d5b3..e24e87ed 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MLBDistSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MLBDistSplit.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 @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -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; @@ -45,12 +44,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Elke Achtert * * @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 */ @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -public class MLBDistSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends MTreeSplit<O, D, N, E> { +public class MLBDistSplit<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends MTreeSplit<O, N, E> { /** * Creates a new split object. */ @@ -70,19 +68,19 @@ public class MLBDistSplit<O, D extends NumberDistance<D, ?>, N extends AbstractM * @param node the node to be split */ @Override - public Assignments<E> split(AbstractMTree<O, D, N, E, ?> tree, N node) { + public Assignments<E> split(AbstractMTree<O, N, E, ?> tree, N node) { DBID firstPromoted = null; DBID secondPromoted = null; // choose first and second routing object double currentMaxDist = 0.; - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { DBID id1 = node.getEntry(i).getRoutingObjectID(); - for (int j = i + 1; j < node.getNumEntries(); j++) { + for(int j = i + 1; j < node.getNumEntries(); j++) { DBID id2 = node.getEntry(j).getRoutingObjectID(); - double distance = tree.distance(id1, id2).doubleValue(); - if (distance >= currentMaxDist) { + double distance = tree.distance(id1, id2); + if(distance >= currentMaxDist) { firstPromoted = id1; secondPromoted = id2; currentMaxDist = distance; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MMRadSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MMRadSplit.java index 232df088..2d3fd7f8 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MMRadSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MMRadSplit.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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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; @@ -44,12 +43,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Elke Achtert * * @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 */ @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -public class MMRadSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends MTreeSplit<O, D, N, E> { +public class MMRadSplit<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends MTreeSplit<O, N, E> { /** * Creates a new split object. */ @@ -67,17 +65,17 @@ public class MMRadSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTr * @param node the node to be split */ @Override - public Assignments<E> split(AbstractMTree<O, D, N, E, ?> tree, N node) { + public Assignments<E> split(AbstractMTree<O, N, E, ?> tree, N node) { double miSumCR = Double.POSITIVE_INFINITY; double[] distanceMatrix = computeDistanceMatrix(tree, node); Assignments<E> bestAssignment = null; - for (int i = 0; i < node.getNumEntries(); i++) { - for (int j = i + 1; j < node.getNumEntries(); j++) { + for(int i = 0; i < node.getNumEntries(); i++) { + for(int j = i + 1; j < node.getNumEntries(); j++) { Assignments<E> currentAssignments = balancedPartition(tree, node, i, j, distanceMatrix); double maxCR = Math.max(currentAssignments.getFirstCoveringRadius(), currentAssignments.getSecondCoveringRadius()); - if (maxCR < miSumCR) { + if(maxCR < miSumCR) { miSumCR = maxCR; bestAssignment = currentAssignments; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MRadSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MRadSplit.java index 5de15356..3feb9d87 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MRadSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/MRadSplit.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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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; @@ -44,12 +43,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Elke Achtert * * @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 */ @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -public class MRadSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends MTreeSplit<O, D, N, E> { +public class MRadSplit<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends MTreeSplit<O, N, E> { /** * Creates a new split object. */ @@ -67,17 +65,17 @@ public class MRadSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTre * @param node the node to be split */ @Override - public Assignments<E> split(AbstractMTree<O, D, N, E, ?> tree, N node) { + public Assignments<E> split(AbstractMTree<O, N, E, ?> tree, N node) { double miSumCR = Double.POSITIVE_INFINITY; double[] distanceMatrix = computeDistanceMatrix(tree, node); Assignments<E> bestAssignment = null; - for (int i = 0; i < node.getNumEntries(); i++) { - for (int j = i + 1; j < node.getNumEntries(); j++) { + for(int i = 0; i < node.getNumEntries(); i++) { + for(int j = i + 1; j < node.getNumEntries(); j++) { Assignments<E> currentAssignments = balancedPartition(tree, node, i, j, distanceMatrix); double sumCR = currentAssignments.getFirstCoveringRadius() + currentAssignments.getSecondCoveringRadius(); - if (sumCR < miSumCR) { + if(sumCR < miSumCR) { miSumCR = sumCR; bestAssignment = currentAssignments; } 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); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/RandomSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/RandomSplit.java index ca54f51a..68a4edd1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/RandomSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/RandomSplit.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 @@ -26,11 +26,10 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split; import java.util.Random; import de.lmu.ifi.dbs.elki.database.ids.DBID; -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; -import de.lmu.ifi.dbs.elki.utilities.RandomFactory; +import de.lmu.ifi.dbs.elki.math.random.RandomFactory; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; @@ -55,12 +54,11 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.RandomParameter; * @author Elke Achtert * * @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 */ @Reference(authors = "P. Ciaccia, M. Patella, P. Zezula", title = "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces", booktitle = "VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece", url = "http://www.vldb.org/conf/1997/P426.PDF") -public class RandomSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends MTreeSplit<O, D, N, E> { +public class RandomSplit<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends MTreeSplit<O, N, E> { /** * Random generator. */ @@ -84,10 +82,10 @@ public class RandomSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMT * @param node the node to be split */ @Override - public Assignments<E> split(AbstractMTree<O, D, N, E, ?> tree, N node) { + public Assignments<E> split(AbstractMTree<O, N, E, ?> tree, N node) { int pos1 = random.nextInt(node.getNumEntries()); int pos2 = random.nextInt(node.getNumEntries() - 1); - if (pos2 >= pos1) { + if(pos2 >= pos1) { ++pos2; } DBID id1 = node.getEntry(pos1).getRoutingObjectID(); @@ -104,11 +102,10 @@ public class RandomSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMT * @apiviz.exclude * * @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 static class Parameterizer<O, D extends NumberDistance<D, ?>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry> extends AbstractParameterizer { + public static class Parameterizer<O, N extends AbstractMTreeNode<O, N, E>, E extends MTreeEntry> extends AbstractParameterizer { /** * Option ID for the random generator. */ @@ -123,13 +120,13 @@ public class RandomSplit<O, D extends NumberDistance<D, ?>, N extends AbstractMT protected void makeOptions(Parameterization config) { super.makeOptions(config); RandomParameter rndP = new RandomParameter(RANDOM_ID); - if (config.grab(rndP)) { + if(config.grab(rndP)) { rnd = rndP.getValue(); } } @Override - protected RandomSplit<O, D, N, E> makeInstance() { + protected RandomSplit<O, N, E> makeInstance() { return new RandomSplit<>(rnd); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/package-info.java index ed0fd729..57c0d978 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/strategies/split/package-info.java @@ -5,7 +5,7 @@ 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 |