diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants')
27 files changed, 265 insertions, 244 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java index 3bac751c..8ede52d7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java @@ -80,7 +80,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Development flag: This will enable some extra integrity checks on the tree. */ - protected final static boolean extraIntegrityChecks = false; + protected static final boolean EXTRA_INTEGRITY_CHECKS = false; /** * The height of this R*-Tree. @@ -93,7 +93,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E public int distanceCalcs = 0; /** - * The last inserted entry + * The last inserted entry. */ E lastInsertedEntry = null; @@ -103,27 +103,27 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E protected BulkSplit bulkSplitter; /** - * The split strategy + * The split strategy. */ protected SplitStrategy nodeSplitter = TopologicalSplitter.STATIC; /** - * The insertion strategy to use + * The insertion strategy to use. */ protected InsertionStrategy insertionStrategy = LeastOverlapInsertionStrategy.STATIC; /** - * Overflow treatment + * Overflow treatment. */ protected OverflowTreatment overflowTreatment = LimitedReinsertOverflowTreatment.RSTAR_OVERFLOW; /** - * Relative minimum fill + * Relative minimum fill. */ protected double relativeMinFill = 0.4; /** - * Constructor + * Constructor. * * @param pagefile Page file */ @@ -132,7 +132,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Set the bulk loading strategy + * Set the bulk loading strategy. * * @param bulkSplitter Bulk loading strategy */ @@ -155,7 +155,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Set insertion strategy + * Set insertion strategy. * * @param insertionStrategy the insertion strategy to set */ @@ -200,7 +200,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E N node = getNode(subtree.getLastPathComponent().getEntry()); if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { - if(((LeafEntry) node.getEntry(i)).getDBID().sameDBID(id)) { + if(DBIDUtil.equal(((LeafEntry) node.getEntry(i)).getDBID(), id)) { return subtree.pathByAddingChild(new TreeIndexPathComponent<E>(node.getEntry(i), i)); } } @@ -319,6 +319,8 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Initializes this R*-Tree from an existing persistent file. + * + * {@inheritDoc} */ @Override public void initializeFromFile(TreeIndexHeader header, PageFile<N> file) { @@ -327,7 +329,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E this.height = computeHeight(); if(getLogger().isDebugging()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append(getClass()); msg.append("\n height = ").append(height); getLogger().debugFine(msg.toString()); @@ -454,8 +456,10 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Performs a bulk load on this RTree with the specified data. Is called by * the constructor. + * + * @param entries Entries to bulk load */ - abstract protected void bulkLoad(List<E> entrys); + protected abstract void bulkLoad(List<E> entries); /** * Returns the height of this R*-Tree. @@ -480,7 +484,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * * @return the height of this RTree */ - abstract protected int computeHeight(); + protected abstract int computeHeight(); /** * Returns true if in the specified node an overflow occurred, false @@ -489,7 +493,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @param node the node to be tested for overflow * @return true if in the specified node an overflow occurred, false otherwise */ - abstract protected boolean hasOverflow(N node); + protected abstract boolean hasOverflow(N node); /** * Returns true if in the specified node an underflow occurred, false @@ -499,7 +503,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @return true if in the specified node an underflow occurred, false * otherwise */ - abstract protected boolean hasUnderflow(N node); + protected abstract boolean hasUnderflow(N node); /** * Creates a new directory entry representing the specified node. @@ -507,7 +511,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @param node the node to be represented by the new entry * @return the newly created directory entry */ - abstract protected E createNewDirectoryEntry(N node); + protected abstract E createNewDirectoryEntry(N node); /** * Creates a new root node that points to the two specified child nodes and @@ -852,7 +856,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // node is root else { - if(hasUnderflow(node) & node.getNumEntries() == 1 && !node.isLeaf()) { + if(hasUnderflow(node) && node.getNumEntries() == 1 && !node.isLeaf()) { N child = getNode(node.getEntry(0)); N newRoot; if(child.isLeaf()) { @@ -889,7 +893,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Determines the entries pointing to the leaf nodes of the specified subtree + * Determines the entries pointing to the leaf nodes of the specified subtree. * * @param node the subtree * @param result the result to store the ids in @@ -914,7 +918,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * Perform additional integrity checks. */ public void doExtraIntegrityChecks() { - if(extraIntegrityChecks) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this); } } @@ -926,7 +930,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E */ @Override public String toString() { - StringBuffer result = new StringBuffer(); + StringBuilder result = new StringBuilder(); int dirNodes = 0; int leafNodes = 0; int objects = 0; @@ -964,7 +968,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E result.append(getClass().getName()).append(" has ").append((levels + 1)).append(" levels.\n"); result.append(dirNodes).append(" Directory Knoten (max = ").append(dirCapacity - 1).append(", min = ").append(dirMinimum).append(")\n"); result.append(leafNodes).append(" Daten Knoten (max = ").append(leafCapacity - 1).append(", min = ").append(leafMinimum).append(")\n"); - result.append(objects).append(" ").append(dim).append("-dim. Punkte im Baum \n"); + result.append(objects).append(' ').append(dim).append("-dim. Punkte im Baum \n"); PageFileUtil.appendPageFileStatistics(result, getPageFileStatistics()); } else { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java index e2bb3abb..ace5ad41 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java @@ -37,8 +37,8 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow. import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.SplitStrategy; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.TopologicalSplitter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint.IntervalBoundary; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -56,31 +56,31 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * @param <E> Entry type * @param <I> Index type */ -public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E> & Index> extends TreeIndexFactory<O, I> { +public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E> & Index> extends TreeIndexFactory<O, I> { /** * Fast-insertion parameter. Optional. */ - public static OptionID INSERTION_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insertionstrategy", "The strategy to use for object insertion."); + public static OptionID INSERTION_STRATEGY_ID = new OptionID("rtree.insertionstrategy", "The strategy to use for object insertion."); /** * Split strategy parameter. Optional. */ - public static OptionID SPLIT_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.splitstrategy", "The strategy to use for node splitting."); + public static OptionID SPLIT_STRATEGY_ID = new OptionID("rtree.splitstrategy", "The strategy to use for node splitting."); /** * Parameter for bulk strategy */ - public static final OptionID BULK_SPLIT_ID = OptionID.getOrCreateOptionID("spatial.bulkstrategy", "The class to perform the bulk split with."); + public static final OptionID BULK_SPLIT_ID = new OptionID("spatial.bulkstrategy", "The class to perform the bulk split with."); /** * Parameter for the relative minimum fill. */ - public static final OptionID MINIMUM_FILL_ID = OptionID.getOrCreateOptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); + public static final OptionID MINIMUM_FILL_ID = new OptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); /** * Overflow treatment. */ - public static OptionID OVERFLOW_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); + public static OptionID OVERFLOW_STRATEGY_ID = new OptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); /** * Strategy to find the insertion node with. @@ -140,7 +140,7 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e * * @apiviz.exclude */ - public static abstract class Parameterizer<O extends NumberVector<O, ?>> extends TreeIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O extends NumberVector<?>> extends TreeIndexFactory.Parameterizer<O> { /** * Insertion strategy */ @@ -170,19 +170,21 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e protected void makeOptions(Parameterization config) { super.makeOptions(config); ObjectParameter<InsertionStrategy> insertionStrategyP = new ObjectParameter<InsertionStrategy>(INSERTION_STRATEGY_ID, InsertionStrategy.class, CombinedInsertionStrategy.class); - if(config.grab(insertionStrategyP)) { + if (config.grab(insertionStrategyP)) { insertionStrategy = insertionStrategyP.instantiateClass(config); } ObjectParameter<SplitStrategy> splitStrategyP = new ObjectParameter<SplitStrategy>(SPLIT_STRATEGY_ID, SplitStrategy.class, TopologicalSplitter.class); - if(config.grab(splitStrategyP)) { + if (config.grab(splitStrategyP)) { nodeSplitter = splitStrategyP.instantiateClass(config); } - DoubleParameter minimumFillP = new DoubleParameter(MINIMUM_FILL_ID, new IntervalConstraint(0.0, IntervalBoundary.OPEN, 0.5, IntervalBoundary.OPEN), 0.4); + DoubleParameter minimumFillP = new DoubleParameter(MINIMUM_FILL_ID, 0.4); + minimumFillP.addConstraint(new GreaterConstraint(0.0)); + minimumFillP.addConstraint(new LessConstraint(0.5)); if (config.grab(minimumFillP)) { minimumFill = minimumFillP.getValue(); } ObjectParameter<OverflowTreatment> overflowP = new ObjectParameter<OverflowTreatment>(OVERFLOW_STRATEGY_ID, OverflowTreatment.class, LimitedReinsertOverflowTreatment.class); - if(config.grab(overflowP)) { + if (config.grab(overflowP)) { overflowTreatment = overflowP.instantiateClass(config); } configBulkLoad(config); @@ -195,7 +197,7 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e */ protected void configBulkLoad(Parameterization config) { ObjectParameter<BulkSplit> bulkSplitP = new ObjectParameter<BulkSplit>(BULK_SPLIT_ID, BulkSplit.class, true); - if(config.grab(bulkSplitP)) { + if (config.grab(bulkSplitP)) { bulkSplitter = bulkSplitP.instantiateClass(config); } } @@ -203,4 +205,4 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e @Override protected abstract AbstractRStarTreeFactory<O, ?, ?, ?> makeInstance(); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java index 46e3003e..80666ebb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java @@ -96,7 +96,7 @@ public abstract class AbstractRStarTreeNode<N extends AbstractRStarTreeNode<N, E if(se.hasMBR()) { final int dim = se.getDimensionality(); // Test for changes - for(int i = 1; i <= dim; i++) { + for(int i = 0; i < dim; i++) { if(Math.abs(se.getMin(i) - mbr.getMin(i)) > Float.MIN_NORMAL) { changed = true; break; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java index 41882ce2..fd7d3d8b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java @@ -120,7 +120,7 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E initialize(spatialObjects.get(0)); } - StringBuffer msg = getLogger().isDebuggingFine() ? new StringBuffer() : null; + StringBuilder msg = getLogger().isDebuggingFine() ? new StringBuilder() : null; // Tiny tree that fits into a single page if(spatialObjects.size() <= leafCapacity) { @@ -165,8 +165,8 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E } if(msg != null) { msg.append("\n height = ").append(getHeight()); - msg.append("\n root " + getRoot()); - getLogger().debugFine(msg.toString() + "\n"); + msg.append("\n root ").append(getRoot()); + getLogger().debugFine(msg.toString()); } } @@ -228,9 +228,9 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E // write to file writeNode(root); if(getLogger().isDebuggingFiner()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append("pageNo ").append(root.getPageID()); - getLogger().debugFiner(msg.toString() + "\n"); + getLogger().debugFiner(msg.toString()); } return root; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java index 9848f121..bc701185 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java @@ -29,23 +29,23 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; /** * Defines the requirements for a leaf entry in an DeLiClu-Tree node. - * Additionally to a leaf entry in an R*-Tree two boolean flags that indicate whether this entry's node - * contains handled or unhandled data objects. - * + * Additionally to a leaf entry in an R*-Tree two boolean flags that indicate + * whether this entry's node contains handled or unhandled data objects. + * * @author Elke Achtert */ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEntry { private static final long serialVersionUID = 1; /** - * Indicates that the node (or its child nodes) which is represented by this entry - * contains handled data objects. + * Indicates that the node (or its child nodes) which is represented by this + * entry contains handled data objects. */ private boolean hasHandled; /** - * Indicates that the node (or its child nodes) which is represented by this entry - * contains unhandled data objects. + * Indicates that the node (or its child nodes) which is represented by this + * entry contains unhandled data objects. */ private boolean hasUnhandled; @@ -53,16 +53,16 @@ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEn * Empty constructor for serialization purposes. */ public DeLiCluLeafEntry() { - // empty constructor + // empty constructor } /** * Constructs a new LeafEntry object with the given parameters. - * - * @param id the unique id of the underlying data object + * + * @param id the unique id of the underlying data object * @param vector the vector to store */ - public DeLiCluLeafEntry(DBID id, NumberVector<?,?> vector) { + public DeLiCluLeafEntry(DBID id, NumberVector<?> vector) { super(id, vector); this.hasHandled = false; this.hasUnhandled = true; @@ -90,7 +90,7 @@ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEn /** * Returns the id as a string representation of this entry. - * + * * @return a string representation of this entry */ @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java index 6f4f782d..0cd74a14 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java @@ -48,7 +48,7 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(DeLiCluTree.class); + private static final Logging LOG = Logging.getLogger(DeLiCluTree.class); /** * Holds the ids of the expanded nodes. @@ -168,6 +168,6 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java index 3f9627a9..b64192c1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java @@ -42,7 +42,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class DeLiCluTreeFactory<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>> { +public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>> { /** * Constructor. * @@ -82,7 +82,7 @@ public class DeLiCluTreeFactory<O extends NumberVector<O, ?>> extends AbstractRS * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { @Override protected DeLiCluTreeFactory<O> makeInstance() { return new DeLiCluTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java index dd3b4d6b..b1216a51 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java @@ -29,6 +29,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; 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.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -52,9 +54,9 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @param <O> Object type */ -public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O> { +public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O> { /** - * The relation we index + * The relation we index. */ private Relation<O> relation; @@ -73,7 +75,7 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree /** * The appropriate logger for this index. */ - private static final Logging logger = Logging.getLogger(DeLiCluTreeIndex.class); + private static final Logging LOG = Logging.getLogger(DeLiCluTreeIndex.class); /** * Creates a new leaf entry representing the specified data object. @@ -93,14 +95,14 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * @return the path of node ids from the root to the objects's parent */ public synchronized List<TreeIndexPathComponent<DeLiCluEntry>> setHandled(DBID id, O obj) { - if(logger.isDebugging()) { - logger.debugFine("setHandled " + id + ", " + obj + "\n"); + if (LOG.isDebugging()) { + LOG.debugFine("setHandled " + id + ", " + obj + "\n"); } // find the leaf node containing o IndexTreePath<DeLiCluEntry> pathToObject = findPathToObject(getRootPath(), obj, id); - if(pathToObject == null) { + if (pathToObject == null) { throw new AbortException("Object not found in setHandled."); } @@ -109,12 +111,12 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree entry.setHasHandled(true); entry.setHasUnhandled(false); - for(IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { + for (IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { DeLiCluEntry parentEntry = path.getParentPath().getLastPathComponent().getEntry(); DeLiCluNode node = getNode(parentEntry); boolean hasHandled = false; boolean hasUnhandled = false; - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { final DeLiCluEntry nodeEntry = node.getEntry(i); hasHandled = hasHandled || nodeEntry.hasHandled(); hasUnhandled = hasUnhandled || nodeEntry.hasUnhandled(); @@ -132,8 +134,8 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * @param id the object id that was inserted */ @Override - public final void insert(DBID id) { - insertLeaf(createNewLeafEntry(id)); + public final void insert(DBIDRef id) { + insertLeaf(createNewLeafEntry(DBIDUtil.deref(id))); } /** @@ -144,21 +146,20 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree */ @Override public final void insertAll(DBIDs ids) { - if(ids.isEmpty() || (ids.size() == 1)) { + if (ids.isEmpty() || (ids.size() == 1)) { return; } // Make an example leaf - if(canBulkLoad()) { + if (canBulkLoad()) { List<DeLiCluEntry> leafs = new ArrayList<DeLiCluEntry>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - leafs.add(createNewLeafEntry(iter.getDBID())); + leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); } bulkLoad(leafs); - } - else { + } else { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - insert(iter.getDBID()); + insert(iter); } } @@ -172,11 +173,11 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * false otherwise */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { // find the leaf node containing o O obj = relation.get(id); IndexTreePath<DeLiCluEntry> deletionPath = findPathToObject(getRootPath(), obj, id); - if(deletionPath == null) { + if (deletionPath == null) { return false; } deletePath(deletionPath); @@ -186,18 +187,18 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override public void deleteAll(DBIDs ids) { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - delete(iter.getDBID()); + delete(DBIDUtil.deref(iter)); } } @Override public <D extends Distance<D>> RangeQuery<O, D> getRangeQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { // Query on the relation we index - if(distanceQuery.getRelation() != relation) { + if (distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if(!(distanceQuery instanceof SpatialDistanceQuery)) { + if (!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; @@ -207,11 +208,11 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override public <D extends Distance<D>> KNNQuery<O, D> getKNNQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { // Query on the relation we index - if(distanceQuery.getRelation() != relation) { + if (distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if(!(distanceQuery instanceof SpatialDistanceQuery)) { + if (!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; @@ -230,6 +231,6 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override protected Logging getLogger() { - return logger; + return LOG; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java index f0acc233..6d539f25 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java @@ -38,11 +38,11 @@ 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.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; 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.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNList; 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.LeafEntry; @@ -51,7 +51,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -102,8 +101,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param object the query object * @param knnList the knn list containing the result */ - protected void doKNNQuery(O object, KNNHeap<DoubleDistance> knnList) { - final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() * 2, 20)); + protected void doKNNQuery(O object, DoubleDistanceKNNHeap knnList) { + final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID())); @@ -120,7 +119,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } } - private double expandNode(O object, KNNHeap<DoubleDistance> knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final Integer nodeID) { + private double expandNode(O object, DoubleDistanceKNNHeap knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -129,8 +128,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend double distance = distanceFunction.doubleMinDist(entry, object); tree.distanceCalcs++; if(distance <= maxDist) { - knnList.add(new DoubleDistanceResultPair(distance, ((LeafEntry) entry).getDBID())); - maxDist = knnList.getKNNDistance().doubleValue(); + knnList.add(distance, ((LeafEntry) entry).getDBID()); + maxDist = knnList.doubleKNNDistance(); } } } @@ -160,20 +159,20 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param node the node for which the query should be performed * @param knnLists a map containing the knn lists for each query objects */ - protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap<DoubleDistance>> knnLists) { + protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, DoubleDistanceKNNHeap> knnLists) { if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry p = node.getEntry(i); - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { final DBID q = ent.getKey(); - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - DoubleDistance knn_q_maxDist = knns_q.getKNNDistance(); + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); DBID pid = ((LeafEntry) p).getDBID(); // FIXME: objects are NOT accessible by DBID in a plain rtree context! - DoubleDistance dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q)); + double dist_pq = distanceFunction.doubleDistance(relation.get(pid), relation.get(q)); tree.distanceCalcs++; - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { + if(dist_pq <= knn_q_maxDist) { knns_q.add(dist_pq, pid); } } @@ -187,13 +186,13 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend List<DoubleDistanceEntry> entries = getSortedEntries(node, ids); for(DoubleDistanceEntry distEntry : entries) { double minDist = distEntry.distance; - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - double knn_q_maxDist = knns_q.getKNNDistance().doubleValue(); + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); if(minDist <= knn_q_maxDist) { SpatialEntry entry = distEntry.entry; - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -264,47 +263,41 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } @Override - public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { + public DoubleDistanceKNNList getKNNForObject(O obj, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final KNNHeap<DoubleDistance> knnList = new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance()); + final DoubleDistanceKNNHeap knnList = new DoubleDistanceKNNHeap(k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @Override - public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { + public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<KNNResult<DoubleDistance>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<DoubleDistanceKNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } // While this works, it seems to be slow at least for large sets! - final Map<DBID, KNNHeap<DoubleDistance>> knnLists = new HashMap<DBID, KNNHeap<DoubleDistance>>(ids.size()); + final Map<DBID, DoubleDistanceKNNHeap> knnLists = new HashMap<DBID, DoubleDistanceKNNHeap>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - knnLists.put(id, new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + DBID id = DBIDUtil.deref(iter); + knnLists.put(id, new DoubleDistanceKNNHeap(k)); } batchNN(tree.getRoot(), knnLists); - List<KNNResult<DoubleDistance>> result = new ArrayList<KNNResult<DoubleDistance>>(); + List<DoubleDistanceKNNList> result = new ArrayList<DoubleDistanceKNNList>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); result.add(knnLists.get(id).toKNNList()); } return result; } - - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<DoubleDistance>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java index 1a861c3e..715b9552 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java @@ -23,16 +23,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; 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.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceDBIDList; 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.LeafEntry; @@ -90,8 +87,8 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<DoubleDistance> doRangeQuery(O object, double epsilon) { - final GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + protected DoubleDistanceDBIDList doRangeQuery(O object, double epsilon) { + final DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(); // push root @@ -104,7 +101,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -113,7 +110,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte if(distance <= epsilon) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new DoubleDistanceResultPair(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -124,7 +121,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java index 09ebb61a..ed7f5949 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java @@ -40,9 +40,11 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.DistanceEntry; @@ -52,7 +54,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -103,7 +104,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param knnList the knn list containing the result */ protected void doKNNQuery(O object, KNNHeap<D> knnList) { - final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() * 2, 20)); + final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new GenericDistanceSearchCandidate<D>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); @@ -120,7 +121,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final Integer nodeID) { + private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -192,7 +193,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis if(minDist.compareTo(knn_q_maxDist) <= 0) { SpatialEntry entry = distEntry.getEntry(); - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -201,12 +202,6 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } - /** * Sorts the entries of the specified node according to their minimum distance * to the specified objects. @@ -238,7 +233,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final KNNHeap<D> knnList = new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance()); + final KNNHeap<D> knnList = KNNUtil.newHeap(distanceFunction, k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @@ -256,14 +251,14 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis // While this works, it seems to be slow at least for large sets! final Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - knnLists.put(iter.getDBID(), new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + knnLists.put(DBIDUtil.deref(iter), KNNUtil.newHeap(distanceFunction, k)); } batchNN(tree.getRoot(), knnLists); List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - result.add(knnLists.get(iter.getDBID()).toKNNList()); + result.add(knnLists.get(DBIDUtil.deref(iter)).toKNNList()); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java index 3b312ed7..a5232b30 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java @@ -23,16 +23,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -89,7 +86,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<D> doRangeQuery(O object, D epsilon) { + protected DistanceDBIDResult<D> doRangeQuery(O object, D epsilon) { final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(); @@ -103,7 +100,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -111,7 +108,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D if(distance.compareTo(epsilon) <= 0) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new GenericDistanceResultPair<D>(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -122,7 +119,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java index 53b32c6b..d63d77cb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java @@ -48,7 +48,7 @@ public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(RStarTree.class); + private static final Logging LOG = Logging.getLogger(RStarTree.class); /** * Constructor. @@ -91,6 +91,6 @@ public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java index 79aac0bd..da7c03fd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java @@ -43,7 +43,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeFactory<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>> { +public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>> { /** * Constructor. * @@ -83,7 +83,7 @@ public class RStarTreeFactory<O extends NumberVector<O, ?>> extends AbstractRSta * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { @Override protected RStarTreeFactory<O> makeInstance() { return new RStarTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java index ab136926..1946293f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java @@ -27,8 +27,9 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; -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.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -52,11 +53,11 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree implements RangeIndex<O>, KNNIndex<O> { +public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree implements RangeIndex<O>, KNNIndex<O> { /** * The appropriate logger for this index. */ - private static final Logging logger = Logging.getLogger(RStarTreeIndex.class); + private static final Logging LOG = Logging.getLogger(RStarTreeIndex.class); /** * Relation @@ -81,8 +82,8 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * @param id Object id * @return Spatial leaf entry */ - protected SpatialPointLeafEntry createNewLeafEntry(DBID id) { - return new SpatialPointLeafEntry(id, relation.get(id)); + protected SpatialPointLeafEntry createNewLeafEntry(DBIDRef id) { + return new SpatialPointLeafEntry(DBIDUtil.deref(id), relation.get(id)); } /** @@ -91,7 +92,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * @param id the object id that was inserted */ @Override - public void insert(DBID id) { + public void insert(DBIDRef id) { insertLeaf(createNewLeafEntry(id)); } @@ -111,13 +112,13 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl if(canBulkLoad()) { List<SpatialEntry> leafs = new ArrayList<SpatialEntry>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - leafs.add(createNewLeafEntry(iter.getDBID())); + leafs.add(createNewLeafEntry(iter)); } bulkLoad(leafs); } else { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - insert(iter.getDBID()); + insert(DBIDUtil.deref(iter)); } } @@ -131,7 +132,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * false otherwise */ @Override - public boolean delete(DBID id) { + public boolean delete(DBIDRef id) { // find the leaf node containing o O obj = relation.get(id); IndexTreePath<SpatialEntry> deletionPath = findPathToObject(getRootPath(), obj, id); @@ -145,7 +146,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl @Override public void deleteAll(DBIDs ids) { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - delete(iter.getDBID()); + delete(iter); } } @@ -189,6 +190,6 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java index 90a8b622..2fd69531 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java @@ -45,7 +45,7 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { /** * Logger. */ - private static final Logging logger = Logging.getLogger(MaxExtensionBulkSplit.class); + private static final Logging LOG = Logging.getLogger(MaxExtensionBulkSplit.class); /** * Static instance @@ -74,12 +74,12 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { List<N> objects = new ArrayList<N>(spatialObjects); while(objects.size() > 0) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); // get the split axis and split point int splitAxis = chooseMaximalExtendedSplitAxis(objects); int splitPoint = chooseBulkSplitPoint(objects.size(), minEntries, maxEntries); - if(logger.isDebugging()) { + if(LOG.isDebugging()) { msg.append("\nsplitAxis ").append(splitAxis); msg.append("\nsplitPoint ").append(splitPoint); } @@ -96,15 +96,15 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { partitions.add(partition1); // copy array - if(logger.isDebugging()) { - msg.append("\ncurrent partition " + partition1); + if(LOG.isDebugging()) { + msg.append("\ncurrent partition ").append(partition1); msg.append("\nremaining objects # ").append(objects.size()); - logger.debugFine(msg.toString()); + LOG.debugFine(msg.toString()); } } - if(logger.isDebugging()) { - logger.debugFine("partitions " + partitions); + if(LOG.isDebugging()) { + LOG.debugFine("partitions " + partitions); } return partitions; } @@ -125,17 +125,17 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { // compute min and max value in each dimension for(SpatialComparable object : objects) { - for(int d = 1; d <= dimension; d++) { + for(int d = 0; d < dimension; d++) { double min, max; min = object.getMin(d); max = object.getMax(d); - if(maxExtension[d - 1] < max) { - maxExtension[d - 1] = max; + if(maxExtension[d] < max) { + maxExtension[d] = max; } - if(minExtension[d - 1] > min) { - minExtension[d - 1] = min; + if(minExtension[d] > min) { + minExtension[d] = min; } } } @@ -143,8 +143,8 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { // set split axis to dim with maximal extension int splitAxis = -1; double max = 0; - for(int d = 1; d <= dimension; d++) { - double currentExtension = maxExtension[d - 1] - minExtension[d - 1]; + for(int d = 0; d < dimension; d++) { + double currentExtension = maxExtension[d] - minExtension[d]; if(max < currentExtension) { max = currentExtension; splitAxis = d; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java index b99ae01e..2209ddef 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java @@ -45,7 +45,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @Reference(authors = "Roussopoulos, N. and Leifker, D.", title = "Direct spatial search on pictorial databases using packed R-trees", booktitle = "ACM SIGMOD Record 14-4", url = "http://dx.doi.org/10.1145/971699.318900") public class OneDimSortBulkSplit extends AbstractBulkSplit { /** - * Static instance + * Static instance. */ public static final AbstractBulkSplit STATIC = new OneDimSortBulkSplit(); @@ -62,8 +62,8 @@ public class OneDimSortBulkSplit extends AbstractBulkSplit { Collections.sort(spatialObjects, new Comparator<SpatialComparable>() { @Override public int compare(SpatialComparable o1, SpatialComparable o2) { - double min1 = (o1.getMax(1) + o1.getMin(1)) / 2; - double min2 = (o2.getMax(1) + o2.getMin(1)) / 2; + double min1 = (o1.getMax(0) + o1.getMin(0)) * .5; + double min2 = (o2.getMax(0) + o2.getMin(0)) * .5; return Double.compare(min1, min2); } }); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java index 28e96da6..e24ef3ce 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java @@ -59,15 +59,15 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { * * @param objs Object list * @param start Subinterval start - * @param end Subinteval end + * @param end Subinterval end * @param depth Iteration depth (must be less than dimensionality!) * @param dims Total number of dimensions * @param maxEntries Maximum page size * @param c Comparison helper * @param ret Output list + * @param <T> data type */ protected <T extends SpatialComparable> void strPartition(List<T> objs, int start, int end, int depth, int dims, int maxEntries, Compare<T> c, List<List<T>> ret) { - c.dim = depth + 1; final int p = (int) Math.ceil((end - start) / (double) maxEntries); final int s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); @@ -78,6 +78,7 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { int e2 = start + (int) (((i + 1) * len) / s); // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); if(e2 < end) { + c.dim = depth; QuickSelect.quickSelect(objs, c, s2, end, e2); } if(depth + 1 == dims) { @@ -101,9 +102,9 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { */ private static class Compare<T extends SpatialComparable> implements Comparator<T> { /** - * Current dimension + * Current dimension. */ - public int dim; + int dim; @Override public int compare(T o1, T o2) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java index 9c3a41a1..beb6e657 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java @@ -82,7 +82,7 @@ public class SpatialSortBulkSplit extends AbstractBulkSplit { /** * Option ID for spatial sorting */ - public static final OptionID SORTER_ID = OptionID.getOrCreateOptionID("rtree.bulk.spatial-sort", "Strategy for spatial sorting in bulk loading."); + public static final OptionID SORTER_ID = new OptionID("rtree.bulk.spatial-sort", "Strategy for spatial sorting in bulk loading."); /** * Sorting class diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java index a1dfbdb0..c39bd914 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java @@ -144,7 +144,7 @@ public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInse /** * Fast-insertion parameter. Optional. */ - public static OptionID INSERTION_CANDIDATES_ID = OptionID.getOrCreateOptionID("rtree.insertion-candidates", "defines how many children are tested for finding the child generating the least overlap when inserting an object."); + public static OptionID INSERTION_CANDIDATES_ID = new OptionID("rtree.insertion-candidates", "defines how many children are tested for finding the child generating the least overlap when inserting an object."); /** * The number of candidates to use @@ -154,7 +154,8 @@ public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInse @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - IntParameter insertionCandidatesP = new IntParameter(INSERTION_CANDIDATES_ID, new GreaterConstraint(0), numCandidates); + IntParameter insertionCandidatesP = new IntParameter(INSERTION_CANDIDATES_ID, numCandidates); + insertionCandidatesP.addConstraint(new GreaterConstraint(0)); if(config.grab(insertionCandidatesP)) { numCandidates = insertionCandidatesP.getValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java index c90d99b2..63bbe9dc 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java @@ -88,12 +88,12 @@ public class CombinedInsertionStrategy implements InsertionStrategy { /** * Insertion strategy for directory nodes. */ - public static final OptionID DIR_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insert-directory", "Insertion strategy for directory nodes."); + public static final OptionID DIR_STRATEGY_ID = new OptionID("rtree.insert-directory", "Insertion strategy for directory nodes."); /** * Insertion strategy for leaf nodes. */ - public static final OptionID LEAF_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insert-leaf", "Insertion strategy for leaf nodes."); + public static final OptionID LEAF_STRATEGY_ID = new OptionID("rtree.insert-leaf", "Insertion strategy for leaf nodes."); /** * Strategy when inserting into directory nodes diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java index 2532f351..3c25cbbc 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java @@ -111,7 +111,7 @@ public class LimitedReinsertOverflowTreatment implements OverflowTreatment { /** * Fast-insertion parameter. Optional. */ - public static OptionID REINSERT_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-strategy", "The strategy to select candidates for reinsertion."); + public static OptionID REINSERT_STRATEGY_ID = new OptionID("rtree.reinsertion-strategy", "The strategy to select candidates for reinsertion."); /** * The actual reinsertion strategy diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java index e0277606..bb222dfe 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java @@ -27,7 +27,8 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDista import de.lmu.ifi.dbs.elki.distance.distancefunction.SquaredEuclideanDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -68,16 +69,16 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { * * @apiviz.exclude */ - public static abstract class Parameterizer extends AbstractParameterizer { + public abstract static class Parameterizer extends AbstractParameterizer { /** * Reinsertion share */ - public static OptionID REINSERT_AMOUNT_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-amount", "The amount of entries to reinsert."); + public static OptionID REINSERT_AMOUNT_ID = new OptionID("rtree.reinsertion-amount", "The amount of entries to reinsert."); /** * Reinsertion share */ - public static OptionID REINSERT_DISTANCE_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-distancce", "The distance function to compute reinsertion candidates by."); + public static OptionID REINSERT_DISTANCE_ID = new OptionID("rtree.reinsertion-distancce", "The distance function to compute reinsertion candidates by."); /** * The actual reinsertion strategy @@ -92,12 +93,14 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - DoubleParameter reinsertAmountP = new DoubleParameter(REINSERT_AMOUNT_ID, new IntervalConstraint(0.0, IntervalConstraint.IntervalBoundary.OPEN, 0.5, IntervalConstraint.IntervalBoundary.OPEN), 0.3); - if(config.grab(reinsertAmountP)) { + DoubleParameter reinsertAmountP = new DoubleParameter(REINSERT_AMOUNT_ID, 0.3); + reinsertAmountP.addConstraint(new GreaterConstraint(0.0)); + reinsertAmountP.addConstraint(new LessConstraint(0.5)); + if (config.grab(reinsertAmountP)) { reinsertAmount = reinsertAmountP.getValue(); } ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); - if(config.grab(distanceP)) { + if (config.grab(distanceP)) { distanceFunction = distanceP.instantiateClass(config); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java index e59fe10e..3e3d599c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java @@ -56,7 +56,7 @@ public class AngTanLinearSplit implements SplitStrategy { /** * Logger class */ - private static final Logging logger = Logging.getLogger(AngTanLinearSplit.class); + private static final Logging LOG = Logging.getLogger(AngTanLinearSplit.class); /** * Static instance. @@ -82,11 +82,11 @@ public class AngTanLinearSplit implements SplitStrategy { } for(int i = 0; i < num; i++) { E e = getter.get(entries, i); - for(int d = 1; d <= dim; d++) { + for(int d = 0; d < dim; d++) { double low = e.getMin(d) - total.getMin(d); double hig = total.getMax(d) - e.getMax(d); if(low >= hig) { - closer[d - 1].set(i); + closer[d].set(i); } } } @@ -105,7 +105,7 @@ public class AngTanLinearSplit implements SplitStrategy { continue; } if(card < bestcard) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = Double.NaN; @@ -117,16 +117,16 @@ public class AngTanLinearSplit implements SplitStrategy { } double overlap = computeOverlap(entries, getter, cand); if(overlap < bestover) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = overlap; } else if(overlap == bestover) { double bestlen = total.getMax(axis) - total.getMin(axis); - double candlen = total.getMax(d + 1) - total.getMin(d + 1); + double candlen = total.getMax(d) - total.getMin(d); if(candlen < bestlen) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = overlap; @@ -135,8 +135,8 @@ public class AngTanLinearSplit implements SplitStrategy { } } if(bestset == null) { - logger.warning("No Ang-Tan-Split found. Probably all points are the same? Returning random split."); - return Util.randomBitSet(num / 2, num, new Random()); + LOG.warning("No Ang-Tan-Split found. Probably all points are the same? Returning random split."); + return Util.randomBitSet(num >> 1, num, new Random()); } return bestset; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java index 7401fbe5..99c15fd6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java @@ -70,72 +70,83 @@ public class GreeneSplit implements SplitStrategy { // Compute individual areas double[] areas = new double[num]; - for(int e1 = 0; e1 < num - 1; e1++) { + for (int e1 = 0; e1 < num - 1; e1++) { final E e1i = getter.get(entries, e1); areas[e1] = SpatialUtil.volume(e1i); } // Compute area increase - for(int e1 = 0; e1 < num - 1; e1++) { + for (int e1 = 0; e1 < num - 1; e1++) { final E e1i = getter.get(entries, e1); - for(int e2 = e1 + 1; e2 < num; e2++) { + for (int e2 = e1 + 1; e2 < num; e2++) { final E e2i = getter.get(entries, e2); final double areaJ = SpatialUtil.volumeUnion(e1i, e2i); final double d = areaJ - areas[e1] - areas[e2]; - if(d > worst) { + if (d > worst) { worst = d; w1 = e1; w2 = e2; } } } - // Data to keep - // Initial mbrs and areas - E m1 = getter.get(entries, w1); - E m2 = getter.get(entries, w2); + if (worst > 0) { + // Data to keep + // Initial mbrs and areas + E m1 = getter.get(entries, w1); + E m2 = getter.get(entries, w2); - double bestsep = Double.NEGATIVE_INFINITY; - double bestsep2 = Double.NEGATIVE_INFINITY; - for(int d = 1; d <= m1.getDimensionality(); d++) { - final double s1 = m1.getMin(d) - m2.getMax(d); - final double s2 = m2.getMin(d) - m1.getMax(d); - final double sm = Math.max(s1, s2); - final double no = Math.max(m1.getMax(d), m2.getMax(d)) - Math.min(m1.getMin(d), m2.getMin(d)); - final double sep = sm / no; - if(sep > bestsep || (sep == bestsep && sm > bestsep2)) { - bestsep = sep; - bestsep2 = sm; - axis = d; + double bestsep = Double.NEGATIVE_INFINITY; + double bestsep2 = Double.NEGATIVE_INFINITY; + for (int d = 0; d < m1.getDimensionality(); d++) { + final double s1 = m1.getMin(d) - m2.getMax(d); + final double s2 = m2.getMin(d) - m1.getMax(d); + final double sm = Math.max(s1, s2); + final double no = Math.max(m1.getMax(d), m2.getMax(d)) - Math.min(m1.getMin(d), m2.getMin(d)); + final double sep = sm / no; + if (sep > bestsep || (sep == bestsep && sm > bestsep2)) { + bestsep = sep; + bestsep2 = sm; + axis = d; + } + } + } else { + // All objects are identical! + final BitSet assignment = new BitSet(num); + final int half = (num + 1) >> 1; + // Put the first half into second node + for (int i = 0; i < half; i++) { + assignment.set(i); } + return assignment; } } // Sort by minimum value DoubleIntPair[] data = new DoubleIntPair[num]; - for(int i = 0; i < num; i++) { + for (int i = 0; i < num; i++) { data[i] = new DoubleIntPair(getter.get(entries, i).getMin(axis), i); } Arrays.sort(data); // Object assignment final BitSet assignment = new BitSet(num); - final int half = (num + 1) / 2; + final int half = (num + 1) >> 1; // Put the first half into second node - for(int i = 0; i < half; i++) { + for (int i = 0; i < half; i++) { assignment.set(data[i].second); } // Tie handling - if(num % 2 == 0) { + if (num % 2 == 0) { // We need to compute the bounding boxes ModifiableHyperBoundingBox mbr1 = new ModifiableHyperBoundingBox(getter.get(entries, data[0].second)); - for(int i = 1; i < half; i++) { + for (int i = 1; i < half; i++) { mbr1.extend(getter.get(entries, data[i].second)); } ModifiableHyperBoundingBox mbr2 = new ModifiableHyperBoundingBox(getter.get(entries, data[num - 1].second)); - for(int i = half + 1; i < num - 1; i++) { + for (int i = half + 1; i < num - 1; i++) { mbr2.extend(getter.get(entries, data[i].second)); } E e = getter.get(entries, data[half].second); double inc1 = SpatialUtil.volumeUnion(mbr1, e) - SpatialUtil.volume(mbr1); double inc2 = SpatialUtil.volumeUnion(mbr2, e) - SpatialUtil.volume(mbr2); - if(inc1 < inc2) { + if (inc1 < inc2) { assignment.set(data[half].second); } } @@ -155,4 +166,4 @@ public class GreeneSplit implements SplitStrategy { return GreeneSplit.STATIC; } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java index 296f6b3b..b4ff2364 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java @@ -67,7 +67,7 @@ public class RTreeLinearSplit implements SplitStrategy { double bestsep = Double.NEGATIVE_INFINITY; int w1 = -1, w2 = -1; // LPS1: find extreme rectangles - for(int d = 1; d <= dim; d++) { + for(int d = 0; d < dim; d++) { // We need to find two candidates each, in case of el==eh! double minlow = Double.POSITIVE_INFINITY; double maxlow = Double.NEGATIVE_INFINITY, maxlow2 = Double.NEGATIVE_INFINITY; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java index 1789ab22..ab32ba19 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java @@ -105,22 +105,25 @@ public class TopologicalSplitter implements SplitStrategy { private A entries; /** - * The getter class for the entries + * The getter class for the entries. */ private ArrayAdapter<E, A> getter; /** - * List size + * List size. */ private int size; /** - * Dimensionality + * Dimensionality. */ private int dimensionality; /** * Constructor. + * + * @param entries Entires to split + * @param getter Array adapter for entries */ public Split(A entries, ArrayAdapter<E, A> getter) { this.entries = entries; @@ -140,7 +143,7 @@ public class TopologicalSplitter implements SplitStrategy { double minSurface = Double.MAX_VALUE; int splitAxis = -1; - for(int d = 1; d <= dimensionality; d++) { + for(int d = 0; d < dimensionality; d++) { double sumOfAllMargins = 0; fillAndSort(d); @@ -180,7 +183,7 @@ public class TopologicalSplitter implements SplitStrategy { } /** - * Init the arrays we use + * Init the arrays we use. */ protected void initMinMaxArrays() { maxSorting = new DoubleIntPair[size]; @@ -227,7 +230,7 @@ public class TopologicalSplitter implements SplitStrategy { // is best for the split axis bestSorting = null; - assert (size - 2 * minEntries > 0) : "Cannot split underfull nodes."; + assert (size - 2 * minEntries >= 0) : "Cannot split nodes (" + size + " < 2*" + minEntries + ")"; // test the sorting with respect to the minimal values { ModifiableHyperBoundingBox mbr1 = mbr(minSorting, 0, minEntries - 1); @@ -267,10 +270,22 @@ public class TopologicalSplitter implements SplitStrategy { assert (splitPoint < size) : "No split found? Volume outside of double precision?"; } + /** + * Get an entry. + * + * @param off Offset + * @return Entry + */ private E get(int off) { return getter.get(entries, off); } + /** + * Get an entry. + * + * @param pair Entry pair + * @return Entry + */ private E get(DoubleIntPair pair) { return getter.get(entries, pair.second); } @@ -306,4 +321,4 @@ public class TopologicalSplitter implements SplitStrategy { return TopologicalSplitter.STATIC; } } -}
\ No newline at end of file +} |