diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants')
62 files changed, 995 insertions, 767 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 8ede52d7..63c8e8fa 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -46,16 +46,11 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndexTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.BulkSplit; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.InsertionStrategy; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.LeastOverlapInsertionStrategy; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.LimitedReinsertOverflowTreatment; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.OverflowTreatment; -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.index.tree.spatial.rstarvariants.util.NodeArrayAdapter; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.logging.statistics.Counter; +import de.lmu.ifi.dbs.elki.logging.statistics.LongStatistic; import de.lmu.ifi.dbs.elki.persistent.PageFile; -import de.lmu.ifi.dbs.elki.persistent.PageFileUtil; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** @@ -68,15 +63,13 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @apiviz.landmark * @apiviz.has AbstractRStarTreeNode oneway - - contains - * @apiviz.composedOf BulkSplit - * @apiviz.composedOf SplitStrategy - * @apiviz.composedOf InsertionStrategy - * @apiviz.composedOf OverflowTreatment + * @apiviz.composedOf AbstractRTreeSettings + * @apiviz.composedOf Statistics * * @param <N> Node type * @param <E> Entry type */ -public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> extends SpatialIndexTree<N, E> { +public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, S extends AbstractRTreeSettings> extends SpatialIndexTree<N, E> { /** * Development flag: This will enable some extra integrity checks on the tree. */ @@ -90,7 +83,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * For counting the number of distance computations. */ - public int distanceCalcs = 0; + public Statistics statistics = new Statistics(); /** * The last inserted entry. @@ -98,92 +91,19 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E E lastInsertedEntry = null; /** - * The strategy for bulk load. + * Settings class. */ - protected BulkSplit bulkSplitter; - - /** - * The split strategy. - */ - protected SplitStrategy nodeSplitter = TopologicalSplitter.STATIC; - - /** - * The insertion strategy to use. - */ - protected InsertionStrategy insertionStrategy = LeastOverlapInsertionStrategy.STATIC; - - /** - * Overflow treatment. - */ - protected OverflowTreatment overflowTreatment = LimitedReinsertOverflowTreatment.RSTAR_OVERFLOW; - - /** - * Relative minimum fill. - */ - protected double relativeMinFill = 0.4; + protected S settings; /** * Constructor. * * @param pagefile Page file + * @param settings Settings */ - public AbstractRStarTree(PageFile<N> pagefile) { + public AbstractRStarTree(PageFile<N> pagefile, S settings) { super(pagefile); - } - - /** - * Set the bulk loading strategy. - * - * @param bulkSplitter Bulk loading strategy - */ - public void setBulkStrategy(BulkSplit bulkSplitter) { - this.bulkSplitter = bulkSplitter; - } - - /** - * Set the node splitting strategy. - * - * @param nodeSplitter the split strategy to set - */ - public void setNodeSplitStrategy(SplitStrategy nodeSplitter) { - if(nodeSplitter != null) { - this.nodeSplitter = nodeSplitter; - } - else { - getLogger().warning("Ignoring setNodeSplitStrategy(null)"); - } - } - - /** - * Set insertion strategy. - * - * @param insertionStrategy the insertion strategy to set - */ - public void setInsertionStrategy(InsertionStrategy insertionStrategy) { - if(insertionStrategy != null) { - this.insertionStrategy = insertionStrategy; - } - else { - getLogger().warning("Ignoring setInsertionStrategy(null)"); - } - } - - /** - * Set the overflow treatment strategy. - * - * @param overflowTreatment overflow treatment strategy - */ - public void setOverflowTreatment(OverflowTreatment overflowTreatment) { - this.overflowTreatment = overflowTreatment; - } - - /** - * Set the relative minimum fill. (Only supported before the tree was used!) - * - * @param relative Relative minimum fill - */ - public void setMinimumFill(double relative) { - this.relativeMinFill = relative; + this.settings = settings; } /** @@ -198,20 +118,20 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E */ protected IndexTreePath<E> findPathToObject(IndexTreePath<E> subtree, SpatialComparable mbr, DBIDRef id) { N node = getNode(subtree.getLastPathComponent().getEntry()); - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - if(DBIDUtil.equal(((LeafEntry) node.getEntry(i)).getDBID(), id)) { - return subtree.pathByAddingChild(new TreeIndexPathComponent<E>(node.getEntry(i), i)); + if (node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { + if (DBIDUtil.equal(((LeafEntry) node.getEntry(i)).getDBID(), id)) { + return subtree.pathByAddingChild(new TreeIndexPathComponent<>(node.getEntry(i), i)); } } } // directory node else { - for(int i = 0; i < node.getNumEntries(); i++) { - if(SpatialUtil.intersects(node.getEntry(i), mbr)) { - IndexTreePath<E> childSubtree = subtree.pathByAddingChild(new TreeIndexPathComponent<E>(node.getEntry(i), i)); + for (int i = 0; i < node.getNumEntries(); i++) { + if (SpatialUtil.intersects(node.getEntry(i), mbr)) { + IndexTreePath<E> childSubtree = subtree.pathByAddingChild(new TreeIndexPathComponent<>(node.getEntry(i), i)); IndexTreePath<E> path = findPathToObject(childSubtree, mbr, id); - if(path != null) { + if (path != null) { return path; } } @@ -222,10 +142,10 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E @Override public void insertLeaf(E leaf) { - if(!initialized) { + if (!initialized) { initialize(leaf); } - overflowTreatment.reinitialize(); + settings.getOverflowTreatment().reinitialize(); preInsert(leaf); insertLeafEntry(leaf); @@ -243,7 +163,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // choose subtree for insertion IndexTreePath<E> subtree = choosePath(getRootPath(), entry, 1); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("insertion-subtree " + subtree); } @@ -266,7 +186,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E lastInsertedEntry = entry; // choose node for insertion of o IndexTreePath<E> subtree = choosePath(getRootPath(), entry, level); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("subtree " + subtree); } @@ -293,20 +213,19 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E writeNode(leaf); // condense the tree - Stack<N> stack = new Stack<N>(); + Stack<N> stack = new Stack<>(); condenseTree(deletionPath.getParentPath(), stack); // reinsert underflow nodes - while(!stack.empty()) { + while (!stack.empty()) { N node = stack.pop(); - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - overflowTreatment.reinitialize(); // Intended? + if (node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { + settings.getOverflowTreatment().reinitialize(); // Intended? this.insertLeafEntry(node.getEntry(i)); } - } - else { - for(int i = 0; i < node.getNumEntries(); i++) { + } else { + for (int i = 0; i < node.getNumEntries(); i++) { stack.push(getNode(node.getEntry(i))); } } @@ -328,7 +247,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // compute height this.height = computeHeight(); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { StringBuilder msg = new StringBuilder(); msg.append(getClass()); msg.append("\n height = ").append(height); @@ -344,15 +263,14 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E ByteArrayOutputStream baos = new ByteArrayOutputStream(); ObjectOutputStream oos = new ObjectOutputStream(baos); SpatialPointLeafEntry sl = new SpatialPointLeafEntry(DBIDUtil.importInteger(0), new double[exampleLeaf.getDimensionality()]); - while(baos.size() <= getPageSize()) { + while (baos.size() <= getPageSize()) { sl.writeExternal(oos); oos.flush(); cap++; } // the last one caused the page to overflow. leafCapacity = cap - 1; - } - catch(IOException e) { + } catch (IOException e) { throw new AbortException("Error determining page sizes.", e); } @@ -363,47 +281,43 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E ObjectOutputStream oos = new ObjectOutputStream(baos); ModifiableHyperBoundingBox hb = new ModifiableHyperBoundingBox(new double[exampleLeaf.getDimensionality()], new double[exampleLeaf.getDimensionality()]); SpatialDirectoryEntry sl = new SpatialDirectoryEntry(0, hb); - while(baos.size() <= getPageSize()) { + while (baos.size() <= getPageSize()) { sl.writeExternal(oos); oos.flush(); cap++; } dirCapacity = cap - 1; - } - catch(IOException e) { + } catch (IOException e) { throw new AbortException("Error determining page sizes.", e); } - if(dirCapacity <= 1) { - throw new IllegalArgumentException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + if (dirCapacity <= 2) { + throw new IllegalArgumentException("Node size of " + getPageSize() + " bytes is chosen too small!"); } - if(dirCapacity < 10) { - getLogger().warning("Page size is choosen very small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + final Logging log = getLogger(); + if (dirCapacity < 10) { + log.warning("Page size is choosen very small! Maximum number of entries in a directory node = " + dirCapacity); } // minimum entries per directory node - dirMinimum = (int) Math.round((dirCapacity - 1) * relativeMinFill); - if(dirMinimum < 2) { - dirMinimum = 2; + dirMinimum = (int) Math.floor(dirCapacity * settings.relativeMinFill); + if (dirMinimum < 1) { + dirMinimum = 1; } - if(leafCapacity <= 1) { - throw new IllegalArgumentException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + if (leafCapacity <= 2) { + throw new IllegalArgumentException("Node size of " + getPageSize() + " bytes is chosen too small!"); } - if(leafCapacity < 10) { - getLogger().warning("Page size is choosen very small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + if (leafCapacity < 10) { + log.warning("Page size is choosen very small! Maximum number of entries in a leaf node = " + leafCapacity); } // minimum entries per leaf node - leafMinimum = (int) Math.round((leafCapacity - 1) * relativeMinFill); - if(leafMinimum < 2) { - leafMinimum = 2; - } - - if(getLogger().isVerbose()) { - getLogger().verbose("Directory Capacity: " + (dirCapacity - 1) + "\nDirectory minimum: " + dirMinimum + "\nLeaf Capacity: " + (leafCapacity - 1) + "\nLeaf Minimum: " + leafMinimum); + leafMinimum = (int) Math.floor(leafCapacity * settings.relativeMinFill); + if (leafMinimum < 1) { + leafMinimum = 1; } } @@ -413,7 +327,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @return Success code */ public boolean canBulkLoad() { - return (bulkSplitter != null && !initialized); + return (settings.bulkSplitter != null && !initialized); } /** @@ -424,17 +338,17 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E */ protected List<E> createBulkLeafNodes(List<E> objects) { int minEntries = leafMinimum; - int maxEntries = leafCapacity - 1; + int maxEntries = leafCapacity; - ArrayList<E> result = new ArrayList<E>(); - List<List<E>> partitions = bulkSplitter.partition(objects, minEntries, maxEntries); + ArrayList<E> result = new ArrayList<>(); + List<List<E>> partitions = settings.bulkSplitter.partition(objects, minEntries, maxEntries); - for(List<E> partition : partitions) { + for (List<E> partition : partitions) { // create leaf node N leafNode = createNewLeafNode(); // insert data - for(E o : partition) { + for (E o : partition) { leafNode.addLeafEntry(o); } // write to file @@ -442,12 +356,12 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E result.add(createNewDirectoryEntry(leafNode)); - if(getLogger().isDebugging()) { - getLogger().debugFine("Created leaf page "+leafNode.getPageID()); + if (getLogger().isDebugging()) { + getLogger().debugFine("Created leaf page " + leafNode.getPageID()); } } - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("numDataPages = " + result.size()); } return result; @@ -528,8 +442,8 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // switch the ids oldRoot.setPageID(root.getPageID()); - if(!oldRoot.isLeaf()) { - for(int i = 0; i < oldRoot.getNumEntries(); i++) { + if (!oldRoot.isLeaf()) { + for (int i = 0; i < oldRoot.getNumEntries(); i++) { N node = getNode(oldRoot.getEntry(i)); writeNode(node); } @@ -544,7 +458,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E writeNode(root); writeNode(oldRoot); writeNode(newNode); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { String msg = "Create new Root: ID=" + root.getPageID(); msg += "\nchild1 " + oldRoot + " " + new HyperBoundingBox(oldRootEntry); msg += "\nchild2 " + newNode + " " + new HyperBoundingBox(newNodeEntry); @@ -552,7 +466,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E getLogger().debugFine(msg); } - return new IndexTreePath<E>(new TreeIndexPathComponent<E>(getRootEntry(), null)); + return new IndexTreePath<>(new TreeIndexPathComponent<>(getRootEntry(), null)); } /** @@ -570,21 +484,20 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E int index = -1; double cEVol = Double.NaN; E ei; - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { ei = node.getEntry(i); // skip test on pairwise overlaps - if(SpatialUtil.contains(ei, mbr)) { - if(containingEntry == null) { + if (SpatialUtil.contains(ei, mbr)) { + if (containingEntry == null) { containingEntry = ei; index = i; - } - else { + } else { double tempVol = SpatialUtil.volume(ei); - if(Double.isNaN(cEVol)) { // calculate volume of currently best + if (Double.isNaN(cEVol)) { // calculate volume of currently best cEVol = SpatialUtil.volume(containingEntry); } // take containing node with lowest volume - if(tempVol < cEVol) { + if (tempVol < cEVol) { cEVol = tempVol; containingEntry = ei; index = i; @@ -592,7 +505,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } } } - return (containingEntry == null ? null : new TreeIndexPathComponent<E>(containingEntry, index)); + return (containingEntry == null ? null : new TreeIndexPathComponent<>(containingEntry, index)); } /** @@ -606,38 +519,36 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @return the path of the appropriate subtree to insert the given mbr */ protected IndexTreePath<E> choosePath(IndexTreePath<E> subtree, SpatialComparable mbr, int level) { - if(getLogger().isDebuggingFiner()) { + if (getLogger().isDebuggingFiner()) { getLogger().debugFiner("node " + subtree + ", level " + level); } N node = getNode(subtree.getLastPathComponent().getEntry()); - if(node == null) { + if (node == null) { throw new RuntimeException("Page file did not return node for node id: " + getPageID(subtree.getLastPathComponent().getEntry())); } - if(node.isLeaf()) { + if (node.isLeaf()) { return subtree; } // first test on containment TreeIndexPathComponent<E> containingEntry = containedTest(node, mbr); - if(containingEntry != null) { + if (containingEntry != null) { IndexTreePath<E> newSubtree = subtree.pathByAddingChild(containingEntry); - if(height - subtree.getPathCount() == level) { + if (height - subtree.getPathCount() == level) { return newSubtree; - } - else { + } else { return choosePath(newSubtree, mbr, level); } } N childNode = getNode(node.getEntry(0)); - int num = insertionStrategy.choose(node, NodeArrayAdapter.STATIC, mbr, height, subtree.getPathCount()); - TreeIndexPathComponent<E> comp = new TreeIndexPathComponent<E>(node.getEntry(num), num); + int num = settings.insertionStrategy.choose(node, NodeArrayAdapter.STATIC, mbr, height, subtree.getPathCount()); + TreeIndexPathComponent<E> comp = new TreeIndexPathComponent<>(node.getEntry(num), num); // children are leafs - if(childNode.isLeaf()) { - if(height - subtree.getPathCount() == level) { + if (childNode.isLeaf()) { + if (height - subtree.getPathCount() == level) { return subtree.pathByAddingChild(comp); - } - else { + } else { throw new IllegalArgumentException("childNode is leaf, but currentLevel != level: " + (height - subtree.getPathCount()) + " != " + level); } } @@ -645,10 +556,9 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E else { IndexTreePath<E> newSubtree = subtree.pathByAddingChild(comp); // desired level is reached - if(height - subtree.getPathCount() == level) { + if (height - subtree.getPathCount() == level) { return newSubtree; - } - else { + } else { return choosePath(newSubtree, mbr, level); } } @@ -666,7 +576,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * reinsertion */ private N overflowTreatment(N node, IndexTreePath<E> path) { - if(overflowTreatment.handleOverflow(this, node, path)) { + if (settings.getOverflowTreatment().handleOverflow(this, node, path)) { return null; } return split(node); @@ -681,14 +591,13 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E private N split(N node) { // choose the split dimension and the split point int minimum = node.isLeaf() ? leafMinimum : dirMinimum; - BitSet split = nodeSplitter.split(node, NodeArrayAdapter.STATIC, minimum); + BitSet split = settings.nodeSplitter.split(node, NodeArrayAdapter.STATIC, minimum); // New node final N newNode; - if(node.isLeaf()) { + if (node.isLeaf()) { newNode = createNewLeafNode(); - } - else { + } else { newNode = createNewDirectoryNode(); } // do the split @@ -712,8 +621,8 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E final int level = height - (path.getPathCount() - 1); BitSet remove = new BitSet(); - List<E> reInsertEntries = new ArrayList<E>(offs.length); - for(int i = 0; i < offs.length; i++) { + List<E> reInsertEntries = new ArrayList<>(offs.length); + for (int i = 0; i < offs.length; i++) { reInsertEntries.add(node.getEntry(offs[i])); remove.set(offs[i]); } @@ -724,30 +633,28 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // and adapt the mbrs IndexTreePath<E> childPath = path; N child = node; - while(childPath.getParentPath() != null) { + while (childPath.getParentPath() != null) { N parent = getNode(childPath.getParentPath().getLastPathComponent().getEntry()); int indexOfChild = childPath.getLastPathComponent().getIndex(); - if(child.adjustEntry(parent.getEntry(indexOfChild))) { + if (child.adjustEntry(parent.getEntry(indexOfChild))) { writeNode(parent); childPath = childPath.getParentPath(); child = parent; - } - else { + } else { break; // TODO: stop writing when MBR didn't change! } } // reinsert the first entries - for(E entry : reInsertEntries) { - if(node.isLeaf()) { - if(getLogger().isDebugging()) { + for (E entry : reInsertEntries) { + if (node.isLeaf()) { + if (getLogger().isDebugging()) { getLogger().debug("reinsert " + entry); } insertLeafEntry(entry); - } - else { - if(getLogger().isDebugging()) { + } else { + if (getLogger().isDebugging()) { getLogger().debug("reinsert " + entry + " at " + level); } insertDirectoryEntry(entry, level); @@ -761,7 +668,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @param subtree the subtree to be adjusted */ protected void adjustTree(IndexTreePath<E> subtree) { - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("Adjust tree " + subtree); } @@ -769,15 +676,15 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E N node = getNode(subtree.getLastPathComponent().getEntry()); // overflow in node - if(hasOverflow(node)) { + if (hasOverflow(node)) { // treatment of overflow: reinsertion or split N split = overflowTreatment(node, subtree); // node was split - if(split != null) { + if (split != null) { // if root was split: create a new root that points the two // split nodes - if(isRoot(node)) { + if (isRoot(node)) { IndexTreePath<E> newRootPath = createNewRoot(node, split); height++; adjustTree(newRootPath); @@ -786,7 +693,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E else { // get the parent and add the new split node N parent = getNode(subtree.getParentPath().getLastPathComponent().getEntry()); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("parent " + parent); } parent.addDirectoryEntry(createNewDirectoryEntry(split)); @@ -807,11 +714,11 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // no overflow, only adjust parameters of the entry representing the // node else { - if(!isRoot(node)) { + if (!isRoot(node)) { N parent = getNode(subtree.getParentPath().getLastPathComponent().getEntry()); E entry = parent.getEntry(subtree.getLastPathComponent().getIndex()); boolean changed = node.adjustEntryIncremental(entry, lastInsertedEntry); - if(changed) { + if (changed) { // node.adjustEntry(parent.getEntry(index)); // write changes in parent to file writeNode(parent); @@ -835,18 +742,16 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E private void condenseTree(IndexTreePath<E> subtree, Stack<N> stack) { N node = getNode(subtree.getLastPathComponent().getEntry()); // node is not root - if(!isRoot(node)) { + if (!isRoot(node)) { N parent = getNode(subtree.getParentPath().getLastPathComponent().getEntry()); int index = subtree.getLastPathComponent().getIndex(); - if(hasUnderflow(node)) { - if(parent.deleteEntry(index)) { + if (hasUnderflow(node)) { + if (parent.deleteEntry(index)) { stack.push(node); - } - else { + } else { node.adjustEntry(parent.getEntry(index)); } - } - else { + } else { node.adjustEntry(parent.getEntry(index)); } writeNode(parent); @@ -856,20 +761,19 @@ 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()) { + if (child.isLeaf()) { newRoot = createNewLeafNode(); newRoot.setPageID(getRootID()); - for(int i = 0; i < child.getNumEntries(); i++) { + for (int i = 0; i < child.getNumEntries(); i++) { newRoot.addLeafEntry(child.getEntry(i)); } - } - else { + } else { newRoot = createNewDirectoryNode(); newRoot.setPageID(getRootID()); - for(int i = 0; i < child.getNumEntries(); i++) { + for (int i = 0; i < child.getNumEntries(); i++) { newRoot.addDirectoryEntry(child.getEntry(i)); } } @@ -881,9 +785,9 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E @Override public final List<E> getLeaves() { - List<E> result = new ArrayList<E>(); + List<E> result = new ArrayList<>(); - if(height == 1) { + if (height == 1) { result.add(getRootEntry()); return result; } @@ -901,13 +805,12 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E */ private void getLeafNodes(N node, List<E> result, int currentLevel) { // Level 1 are the leaf nodes, Level 2 is the one atop! - if(currentLevel == 2) { - for(int i = 0; i < node.getNumEntries(); i++) { + if (currentLevel == 2) { + for (int i = 0; i < node.getNumEntries(); i++) { result.add(node.getEntry(i)); } - } - else { - for(int i = 0; i < node.getNumEntries(); i++) { + } else { + for (int i = 0; i < node.getNumEntries(); i++) { N child = getNode(node.getEntry(i)); getLeafNodes(child, result, (currentLevel - 1)); } @@ -918,11 +821,100 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * Perform additional integrity checks. */ public void doExtraIntegrityChecks() { - if(EXTRA_INTEGRITY_CHECKS) { + if (EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this); } } + @Override + public void logStatistics() { + super.logStatistics(); + Logging log = getLogger(); + if (log.isStatistics()) { + log.statistics(new LongStatistic(this.getClass().getName() + ".height", height)); + statistics.logStatistics(); + } + } + + /** + * Class for tracking some statistics. + * + * @author Erich Schubert + * + * @apiviz.composedOf Counter + */ + public class Statistics { + /** + * For counting the number of distance computations. + */ + protected final Counter distanceCalcs; + + /** + * For counting the number of knn queries answered. + */ + protected final Counter knnQueries; + + /** + * For counting the number of range queries answered. + */ + protected final Counter rangeQueries; + + /** + * Constructor. + */ + public Statistics() { + super(); + Logging log = getLogger(); + final String prefix = AbstractRStarTree.this.getClass().getName(); + distanceCalcs = log.isStatistics() ? log.newCounter(prefix + ".distancecalcs") : null; + knnQueries = log.isStatistics() ? log.newCounter(prefix + ".knnqueries") : null; + rangeQueries = log.isStatistics() ? log.newCounter(prefix + ".rangequeries") : null; + } + + /** + * Count a distance computation. + */ + public void countDistanceCalculation() { + if (distanceCalcs != null) { + distanceCalcs.increment(); + } + } + + /** + * Count a knn query invocation. + */ + public void countKNNQuery() { + if (knnQueries != null) { + knnQueries.increment(); + } + } + + /** + * Count a range query invocation. + */ + public void countRangeQuery() { + if (rangeQueries != null) { + rangeQueries.increment(); + } + } + + /** + * Log the statistics. + */ + public void logStatistics() { + Logging log = getLogger(); + if (statistics.distanceCalcs != null) { + log.statistics(statistics.distanceCalcs); + } + if (statistics.knnQueries != null) { + log.statistics(statistics.knnQueries); + } + if (statistics.rangeQueries != null) { + log.statistics(statistics.rangeQueries); + } + } + } + /** * Returns a string representation of this R*-Tree. * @@ -936,45 +928,42 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E int objects = 0; int levels = 0; - if(initialized) { + if (initialized) { N node = getRoot(); int dim = getRootEntry().getDimensionality(); - while(!node.isLeaf()) { - if(node.getNumEntries() > 0) { + while (!node.isLeaf()) { + if (node.getNumEntries() > 0) { E entry = node.getEntry(0); node = getNode(entry); levels++; } } - BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<N, E>(this, getRootPath()); - while(enumeration.hasMoreElements()) { + BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<>(this, getRootPath()); + while (enumeration.hasMoreElements()) { IndexTreePath<E> indexPath = enumeration.nextElement(); E entry = indexPath.getLastPathComponent().getEntry(); - if(entry.isLeafEntry()) { + if (entry.isLeafEntry()) { objects++; - } - else { + } else { node = getNode(entry); - if(node.isLeaf()) { + if (node.isLeaf()) { leafNodes++; - } - else { + } else { dirNodes++; } } } 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(dirNodes).append(" Directory Knoten (max = ").append(dirCapacity).append(", min = ").append(dirMinimum).append(")\n"); + result.append(leafNodes).append(" Daten Knoten (max = ").append(leafCapacity).append(", min = ").append(leafMinimum).append(")\n"); result.append(objects).append(' ').append(dim).append("-dim. Punkte im Baum \n"); - PageFileUtil.appendPageFileStatistics(result, getPageFileStatistics()); - } - else { + // PageFileUtil.appendPageFileStatistics(result, getPageFileStatistics()); + } else { result.append(getClass().getName()).append(" is empty!\n"); } return result.toString(); } -}
\ No newline at end of file +} 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 ace5ad41..48b84302 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,7 +27,7 @@ import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.data.type.TypeUtil; import de.lmu.ifi.dbs.elki.index.Index; -import de.lmu.ifi.dbs.elki.index.tree.TreeIndexFactory; +import de.lmu.ifi.dbs.elki.index.PagedIndexFactory; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.BulkSplit; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.CombinedInsertionStrategy; @@ -36,6 +36,7 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow. import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.OverflowTreatment; 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.persistent.PageFileFactory; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint; @@ -56,76 +57,21 @@ 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<?>, 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, S> & Index, S extends AbstractRTreeSettings> extends PagedIndexFactory<O, I> { /** - * Fast-insertion parameter. Optional. + * Tree settings */ - 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 = new OptionID("rtree.splitstrategy", "The strategy to use for node splitting."); - - /** - * Parameter for bulk strategy - */ - 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 = new OptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); - - /** - * Overflow treatment. - */ - public static OptionID OVERFLOW_STRATEGY_ID = new OptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); - - /** - * Strategy to find the insertion node with. - */ - protected InsertionStrategy insertionStrategy; - - /** - * The strategy for bulk load. - */ - protected BulkSplit bulkSplitter; - - /** - * The strategy for splitting nodes - */ - protected SplitStrategy nodeSplitter; - - /** - * Overflow treatment strategy - */ - protected OverflowTreatment overflowTreatment; - - /** - * Relative minimum fill - */ - protected double minimumFill; + protected S settings; /** * Constructor. * - * @param fileName - * @param pageSize - * @param cacheSize - * @param bulkSplitter the strategy to use for bulk splitting - * @param insertionStrategy the strategy to find the insertion child - * @param nodeSplitter the strategy to use for splitting nodes - * @param overflowTreatment the strategy to use for overflow treatment - * @param minimumFill the relative minimum fill + * @param pageFileFactory Page file factory + * @param settings Tree settings */ - public AbstractRStarTreeFactory(String fileName, int pageSize, long cacheSize, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy, SplitStrategy nodeSplitter, OverflowTreatment overflowTreatment, double minimumFill) { - super(fileName, pageSize, cacheSize); - this.insertionStrategy = insertionStrategy; - this.bulkSplitter = bulkSplitter; - this.nodeSplitter = nodeSplitter; - this.overflowTreatment = overflowTreatment; - this.minimumFill = minimumFill; + public AbstractRStarTreeFactory(PageFileFactory<?> pageFileFactory, S settings) { + super(pageFileFactory); + this.settings = settings; } @Override @@ -139,53 +85,69 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N exte * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type + * @param <S> Settings class */ - public abstract static class Parameterizer<O extends NumberVector<?>> extends TreeIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O extends NumberVector<?>, S extends AbstractRTreeSettings> extends PagedIndexFactory.Parameterizer<O> { + /** + * Fast-insertion parameter. Optional. + */ + public static OptionID INSERTION_STRATEGY_ID = new OptionID("rtree.insertionstrategy", "The strategy to use for object insertion."); + /** - * Insertion strategy + * Split strategy parameter. Optional. */ - protected InsertionStrategy insertionStrategy = null; + public static OptionID SPLIT_STRATEGY_ID = new OptionID("rtree.splitstrategy", "The strategy to use for node splitting."); /** - * The strategy for splitting nodes + * Parameter for bulk strategy */ - protected SplitStrategy nodeSplitter = null; + public static final OptionID BULK_SPLIT_ID = new OptionID("spatial.bulkstrategy", "The class to perform the bulk split with."); /** - * Bulk loading strategy + * Parameter for the relative minimum fill. */ - protected BulkSplit bulkSplitter = null; + public static final OptionID MINIMUM_FILL_ID = new OptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); /** - * Overflow treatment strategy + * Overflow treatment. */ - protected OverflowTreatment overflowTreatment = null; + public static OptionID OVERFLOW_STRATEGY_ID = new OptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); /** - * Relative minimum fill + * Tree settings + */ + protected S settings; + + /** + * Create the settings object + * + * @return Settings instance. */ - protected double minimumFill; + abstract protected S createSettings(); @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - ObjectParameter<InsertionStrategy> insertionStrategyP = new ObjectParameter<InsertionStrategy>(INSERTION_STRATEGY_ID, InsertionStrategy.class, CombinedInsertionStrategy.class); + settings = createSettings(); + ObjectParameter<InsertionStrategy> insertionStrategyP = new ObjectParameter<>(INSERTION_STRATEGY_ID, InsertionStrategy.class, CombinedInsertionStrategy.class); if (config.grab(insertionStrategyP)) { - insertionStrategy = insertionStrategyP.instantiateClass(config); + settings.insertionStrategy = insertionStrategyP.instantiateClass(config); } - ObjectParameter<SplitStrategy> splitStrategyP = new ObjectParameter<SplitStrategy>(SPLIT_STRATEGY_ID, SplitStrategy.class, TopologicalSplitter.class); + ObjectParameter<SplitStrategy> splitStrategyP = new ObjectParameter<>(SPLIT_STRATEGY_ID, SplitStrategy.class, TopologicalSplitter.class); if (config.grab(splitStrategyP)) { - nodeSplitter = splitStrategyP.instantiateClass(config); + settings.nodeSplitter = splitStrategyP.instantiateClass(config); } 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(); + settings.relativeMinFill = minimumFillP.getValue(); } - ObjectParameter<OverflowTreatment> overflowP = new ObjectParameter<OverflowTreatment>(OVERFLOW_STRATEGY_ID, OverflowTreatment.class, LimitedReinsertOverflowTreatment.class); + ObjectParameter<OverflowTreatment> overflowP = new ObjectParameter<>(OVERFLOW_STRATEGY_ID, OverflowTreatment.class, LimitedReinsertOverflowTreatment.class); if (config.grab(overflowP)) { - overflowTreatment = overflowP.instantiateClass(config); + settings.setOverflowTreatment(overflowP.instantiateClass(config)); } configBulkLoad(config); } @@ -196,13 +158,13 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N exte * @param config Parameterization */ protected void configBulkLoad(Parameterization config) { - ObjectParameter<BulkSplit> bulkSplitP = new ObjectParameter<BulkSplit>(BULK_SPLIT_ID, BulkSplit.class, true); + ObjectParameter<BulkSplit> bulkSplitP = new ObjectParameter<>(BULK_SPLIT_ID, BulkSplit.class, true); if (config.grab(bulkSplitP)) { - bulkSplitter = bulkSplitP.instantiateClass(config); + settings.bulkSplitter = bulkSplitP.instantiateClass(config); } } @Override - protected abstract AbstractRStarTreeFactory<O, ?, ?, ?> makeInstance(); + protected abstract AbstractRStarTreeFactory<O, ?, ?, ?, ?> makeInstance(); } } 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 80666ebb..6b5fc2f0 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -133,7 +133,7 @@ public abstract class AbstractRStarTreeNode<N extends AbstractRStarTreeNode<N, E * Tests this node (for debugging purposes). */ @SuppressWarnings("unchecked") - public final void integrityCheck(AbstractRStarTree<N, E> tree) { + public final void integrityCheck(AbstractRStarTree<N, E, ?> tree) { // leaf node if(isLeaf()) { for(int i = 0; i < getCapacity(); i++) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java new file mode 100644 index 00000000..f876be13 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java @@ -0,0 +1,121 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; + +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.BulkSplit; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.InsertionStrategy; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.LeastOverlapInsertionStrategy; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.LimitedReinsertOverflowTreatment; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.OverflowTreatment; +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; + +/* + 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/>. + */ + +/** + * Class to wrap common Rtree settings. + * + * @author Erich Schubert + * + * @apiviz.composedOf BulkSplit + * @apiviz.composedOf SplitStrategy + * @apiviz.composedOf InsertionStrategy + * @apiviz.composedOf OverflowTreatment + */ +public class AbstractRTreeSettings { + /** + * The strategy for bulk load. + */ + protected BulkSplit bulkSplitter = null; + + /** + * The split strategy. + */ + protected SplitStrategy nodeSplitter = TopologicalSplitter.STATIC; + + /** + * The insertion strategy to use. + */ + protected InsertionStrategy insertionStrategy = LeastOverlapInsertionStrategy.STATIC; + + /** + * Overflow treatment. + */ + private OverflowTreatment overflowTreatment = LimitedReinsertOverflowTreatment.RSTAR_OVERFLOW; + + /** + * Relative minimum fill. + */ + protected double relativeMinFill = 0.4; + + /** + * Set the bulk loading strategy. + * + * @param bulkSplitter Bulk loading strategy + */ + public void setBulkStrategy(BulkSplit bulkSplitter) { + this.bulkSplitter = bulkSplitter; + } + + /** + * Set the node splitting strategy. + * + * @param nodeSplitter the split strategy to set + */ + public void setNodeSplitStrategy(SplitStrategy nodeSplitter) { + this.nodeSplitter = nodeSplitter; + } + + /** + * Set insertion strategy. + * + * @param insertionStrategy the insertion strategy to set + */ + public void setInsertionStrategy(InsertionStrategy insertionStrategy) { + this.insertionStrategy = insertionStrategy; + } + + /** + * Set the overflow treatment strategy. + * + * @param overflowTreatment overflow treatment strategy + */ + public void setOverflowTreatment(OverflowTreatment overflowTreatment) { + this.overflowTreatment = overflowTreatment; + } + + /** + * Set the relative minimum fill. (Only supported before the tree was used!) + * + * @param relative Relative minimum fill + */ + public void setMinimumFill(double relative) { + this.relativeMinFill = relative; + } + + /** + * @return the overflowTreatment + */ + public OverflowTreatment getOverflowTreatment() { + return overflowTreatment; + } +} 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 fd7d3d8b..8a4f530f 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -38,14 +38,15 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * @param <N> Node type * @param <E> Entry type */ -public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> extends AbstractRStarTree<N, E> { +public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, S extends AbstractRTreeSettings> extends AbstractRStarTree<N, E, S> { /** * Constructor. * * @param pagefile Page file + * @param settings Settings */ - public NonFlatRStarTree(PageFile<N> pagefile) { - super(pagefile); + public NonFlatRStarTree(PageFile<N> pagefile, S settings) { + super(pagefile, settings); } /** @@ -180,8 +181,8 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E int minEntries = dirMinimum; int maxEntries = dirCapacity - 1; - ArrayList<E> result = new ArrayList<E>(); - List<List<E>> partitions = bulkSplitter.partition(nodes, minEntries, maxEntries); + ArrayList<E> result = new ArrayList<>(); + List<List<E>> partitions = settings.bulkSplitter.partition(nodes, minEntries, maxEntries); for(List<E> partition : partitions) { // create node diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java index 10f25ec0..510120c9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/deliclu/DeLiCluEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java index 8b279268..f72b7d8d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java index bc701185..741ab840 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/deliclu/DeLiCluNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java index bf993c01..7b3221c3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/deliclu/DeLiCluTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java index 0cd74a14..33366763 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,19 +23,19 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.HashMap; -import java.util.HashSet; -import java.util.Set; - +import gnu.trove.map.hash.TIntObjectHashMap; +import gnu.trove.set.TIntSet; +import gnu.trove.set.hash.TIntHashSet; import de.lmu.ifi.dbs.elki.index.tree.BreadthFirstEnumeration; import de.lmu.ifi.dbs.elki.index.tree.Entry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; /** - * DeLiCluTree is a spatial index structure based on an R-TRee. DeLiCluTree is + * DeLiCluTree is a spatial index structure based on an R-Tree. DeLiCluTree is * designed for the DeLiClu algorithm, having in each node a boolean array which * indicates whether the child nodes are already handled by the DeLiClu * algorithm. @@ -44,7 +44,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @apiviz.has DeLiCluNode oneway - - contains */ -public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { +public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry, AbstractRTreeSettings> { /** * The logger for this class. */ @@ -53,15 +53,16 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { /** * Holds the ids of the expanded nodes. */ - private HashMap<Integer, HashSet<Integer>> expanded = new HashMap<Integer, HashSet<Integer>>(); + private TIntObjectHashMap<TIntHashSet> expanded = new TIntObjectHashMap<>(); /** * Constructor. * * @param pagefile Page file + * @param settings Settings */ - public DeLiCluTree(PageFile<DeLiCluNode> pagefile) { - super(pagefile); + public DeLiCluTree(PageFile<DeLiCluNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); } /** @@ -71,9 +72,9 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { * @param entry2 the second node */ public void setExpanded(SpatialEntry entry1, SpatialEntry entry2) { - HashSet<Integer> exp1 = expanded.get(getPageID(entry1)); + TIntHashSet exp1 = expanded.get(getPageID(entry1)); if(exp1 == null) { - exp1 = new HashSet<Integer>(); + exp1 = new TIntHashSet(); expanded.put(getPageID(entry1), exp1); } exp1.add(getPageID(entry2)); @@ -85,12 +86,12 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { * @param entry the id of the node for which the expansions should be returned * @return the nodes which are already expanded with the specified node */ - public Set<Integer> getExpanded(SpatialEntry entry) { - HashSet<Integer> exp = expanded.get(getPageID(entry)); + public TIntSet getExpanded(SpatialEntry entry) { + TIntHashSet exp = expanded.get(getPageID(entry)); if(exp != null) { return exp; } - return new HashSet<Integer>(); + return new TIntHashSet(); } /** @@ -99,12 +100,12 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { * @param entry the id of the node for which the expansions should be returned * @return the nodes which are already expanded with the specified node */ - public Set<Integer> getExpanded(DeLiCluNode entry) { - HashSet<Integer> exp = expanded.get(entry.getPageID()); + public TIntSet getExpanded(DeLiCluNode entry) { + TIntHashSet exp = expanded.get(entry.getPageID()); if(exp != null) { return exp; } - return new HashSet<Integer>(); + return new TIntHashSet(); } /** @@ -115,7 +116,7 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { public int numNodes() { int numNodes = 0; - BreadthFirstEnumeration<DeLiCluNode, DeLiCluEntry> bfs = new BreadthFirstEnumeration<DeLiCluNode, DeLiCluEntry>(this, getRootPath()); + BreadthFirstEnumeration<DeLiCluNode, DeLiCluEntry> bfs = new BreadthFirstEnumeration<>(this, getRootPath()); while(bfs.hasMoreElements()) { Entry entry = bfs.nextElement().getLastPathComponent().getEntry(); if(!entry.isLeafEntry()) { @@ -170,4 +171,4 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { protected Logging getLogger() { 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 b64192c1..a63b8004 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,11 +26,9 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeFactory; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.BulkSplit; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.InsertionStrategy; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.OverflowTreatment; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.SplitStrategy; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; /** * Factory for DeLiClu R*-Trees. @@ -42,32 +40,21 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>> { +public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>, AbstractRTreeSettings> { /** * Constructor. * - * @param fileName - * @param pageSize - * @param cacheSize - * @param bulkSplitter Bulk loading strategy - * @param insertionStrategy the strategy to find the insertion child - * @param nodeSplitter the strategy for splitting nodes. - * @param overflowTreatment the strategy to use for overflow treatment - * @param minimumFill the relative minimum fill + * @param pageFileFactory Page file factory + * @param settings Settings */ - public DeLiCluTreeFactory(String fileName, int pageSize, long cacheSize, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy, SplitStrategy nodeSplitter, OverflowTreatment overflowTreatment, double minimumFill) { - super(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); + public DeLiCluTreeFactory(PageFileFactory<?> pageFileFactory, AbstractRTreeSettings settings) { + super(pageFileFactory, settings); } @Override public DeLiCluTreeIndex<O> instantiate(Relation<O> relation) { PageFile<DeLiCluNode> pagefile = makePageFile(getNodeClass()); - DeLiCluTreeIndex<O> index = new DeLiCluTreeIndex<O>(relation, pagefile); - index.setBulkStrategy(bulkSplitter); - index.setInsertionStrategy(insertionStrategy); - index.setNodeSplitStrategy(nodeSplitter); - index.setOverflowTreatment(overflowTreatment); - index.setMinimumFill(minimumFill); + DeLiCluTreeIndex<O> index = new DeLiCluTreeIndex<>(relation, pagefile, settings); return index; } @@ -82,10 +69,15 @@ public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStar * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { @Override protected DeLiCluTreeFactory<O> makeInstance() { - return new DeLiCluTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); + return new DeLiCluTreeFactory<>(pageFileFactory, settings); + } + + @Override + protected AbstractRTreeSettings createSettings() { + return new AbstractRTreeSettings(); } } -}
\ No newline at end of file +} 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 b1216a51..67c9c9e0 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -38,10 +38,12 @@ 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.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; 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.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -54,7 +56,7 @@ 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>, DynamicIndex { /** * The relation we index. */ @@ -65,11 +67,11 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp * * @param relation Relation to index * @param pagefile Page file + * @param settings Tree settings */ - public DeLiCluTreeIndex(Relation<O> relation, PageFile<DeLiCluNode> pagefile) { - super(pagefile); + public DeLiCluTreeIndex(Relation<O> relation, PageFile<DeLiCluNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); this.relation = relation; - this.initialize(); } /** @@ -128,6 +130,12 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp return pathToObject.getPath(); } + @Override + public void initialize() { + super.initialize(); + insertAll(relation.getDBIDs()); + } + /** * Inserts the specified real vector object into this index. * @@ -152,7 +160,7 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp // Make an example leaf if (canBulkLoad()) { - List<DeLiCluEntry> leafs = new ArrayList<DeLiCluEntry>(ids.size()); + List<DeLiCluEntry> leafs = new ArrayList<>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java index b6c0af9b..f8bec8cb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 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/spatial/rstarvariants/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java index 2774fbe1..e50cc513 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 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/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java index 6d539f25..b7769d45 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -34,15 +34,14 @@ import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; 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.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; 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.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; @@ -50,7 +49,7 @@ import de.lmu.ifi.dbs.elki.index.tree.query.DoubleDistanceSearchCandidate; 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.ComparableMinHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -73,7 +72,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend /** * The index to use */ - protected final AbstractRStarTree<?, ?> tree; + protected final AbstractRStarTree<?, ?, ?> tree; /** * Spatial primitive distance function @@ -87,7 +86,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param distanceQuery Distance query to use * @param distanceFunction Distance function */ - public DoubleDistanceRStarTreeKNNQuery(AbstractRStarTree<?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { + public DoubleDistanceRStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { super(distanceQuery); this.tree = tree; this.distanceFunction = distanceFunction; @@ -102,7 +101,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param knnList the knn list containing the result */ protected void doKNNQuery(O object, DoubleDistanceKNNHeap knnList) { - final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() << 1, 20)); + final ComparableMinHeap<DoubleDistanceSearchCandidate> pq = new ComparableMinHeap<>(Math.min(knnList.getK() << 1, 21)); + tree.statistics.countKNNQuery(); // push root pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID())); @@ -119,14 +119,14 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } } - private double expandNode(O object, DoubleDistanceKNNHeap knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { + private double expandNode(O object, DoubleDistanceKNNHeap knnList, final ComparableMinHeap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); double distance = distanceFunction.doubleMinDist(entry, object); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); if(distance <= maxDist) { knnList.add(distance, ((LeafEntry) entry).getDBID()); maxDist = knnList.doubleKNNDistance(); @@ -138,7 +138,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); double distance = distanceFunction.doubleMinDist(entry, object); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); // Greedy expand, bypassing the queue if(distance <= 0) { expandNode(object, knnList, pq, maxDist, ((DirectoryEntry) entry).getPageID()); @@ -169,9 +169,10 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend double knn_q_maxDist = knns_q.doubleKNNDistance(); DBID pid = ((LeafEntry) p).getDBID(); - // FIXME: objects are NOT accessible by DBID in a plain rtree context! + // FIXME: objects are NOT accessible by DBID in a plain R-tree + // context! double dist_pq = distanceFunction.doubleDistance(relation.get(pid), relation.get(q)); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); if(dist_pq <= knn_q_maxDist) { knns_q.add(dist_pq, pid); } @@ -210,14 +211,14 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @return a list of the sorted entries */ protected List<DoubleDistanceEntry> getSortedEntries(AbstractRStarTreeNode<?, ?> node, DBIDs ids) { - List<DoubleDistanceEntry> result = new ArrayList<DoubleDistanceEntry>(); + List<DoubleDistanceEntry> result = new ArrayList<>(); for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); double minMinDist = Double.MAX_VALUE; - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { double minDist = distanceFunction.doubleMinDist(entry, relation.get(iter)); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); minMinDist = Math.min(minDist, minMinDist); } result.add(new DoubleDistanceEntry(entry, minMinDist)); @@ -268,34 +269,30 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final DoubleDistanceKNNHeap knnList = new DoubleDistanceKNNHeap(k); + final DoubleDistanceKNNHeap knnList = (DoubleDistanceKNNHeap) DBIDUtil.newHeap(DoubleDistance.FACTORY, k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @Override - public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) { - return getKNNForObject(relation.get(id), k); - } - - @Override 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, DoubleDistanceKNNHeap> knnLists = new HashMap<DBID, DoubleDistanceKNNHeap>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + final Map<DBID, DoubleDistanceKNNHeap> knnLists = new HashMap<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); - knnLists.put(id, new DoubleDistanceKNNHeap(k)); + knnLists.put(id, (DoubleDistanceKNNHeap) DBIDUtil.newHeap(DoubleDistance.FACTORY, k)); } batchNN(tree.getRoot(), knnLists); - List<DoubleDistanceKNNList> result = new ArrayList<DoubleDistanceKNNList>(); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + List<DoubleDistanceKNNList> result = new ArrayList<>(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); + tree.statistics.countKNNQuery(); result.add(knnLists.get(id).toKNNList()); } return result; 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 715b9552..eb85574f 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,19 +24,19 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; */ 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.ids.distance.DistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPairList; 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; import de.lmu.ifi.dbs.elki.index.tree.query.DoubleDistanceSearchCandidate; 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.ComparableMinHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -60,7 +60,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte /** * The index to use */ - protected final AbstractRStarTree<?, ?> tree; + protected final AbstractRStarTree<?, ?, ?> tree; /** * Spatial primitive distance function @@ -74,7 +74,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @param distanceQuery Distance query to use * @param distanceFunction Distance function */ - public DoubleDistanceRStarTreeRangeQuery(AbstractRStarTree<?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { + public DoubleDistanceRStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { super(distanceQuery); this.tree = tree; this.distanceFunction = distanceFunction; @@ -88,8 +88,9 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @return Objects contained in query range. */ protected DoubleDistanceDBIDList doRangeQuery(O object, double epsilon) { - final DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); - final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(); + tree.statistics.countRangeQuery(); + final DoubleDistanceDBIDPairList result = new DoubleDistanceDBIDPairList(); + final ComparableMinHeap<DoubleDistanceSearchCandidate> pq = new ComparableMinHeap<>(); // push root pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID())); @@ -101,12 +102,12 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { double distance = distanceFunction.doubleMinDist(object, node.getEntry(i)); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); if(distance <= epsilon) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); @@ -126,12 +127,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte } @Override - public DistanceDBIDResult<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { + public DistanceDBIDList<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { return doRangeQuery(obj, range.doubleValue()); } - - @Override - public DistanceDBIDResult<DoubleDistance> getRangeForDBID(DBIDRef id, DoubleDistance range) { - return getRangeForObject(relation.get(id), range); - } }
\ No newline at end of file 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 ed7f5949..f520d52f 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -34,27 +34,25 @@ import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; 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.ids.ModifiableDBIDs; +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.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; 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; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; import de.lmu.ifi.dbs.elki.index.tree.query.GenericDistanceSearchCandidate; 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.ComparableMinHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.pairs.FCPair; /** * Instance of a KNN query for a particular spatial index. @@ -76,7 +74,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis /** * The index to use */ - protected final AbstractRStarTree<?, ?> tree; + protected final AbstractRStarTree<?, ?, ?> tree; /** * Spatial primitive distance function @@ -89,7 +87,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param tree Index to use * @param distanceQuery Distance query to use */ - public GenericRStarTreeKNNQuery(AbstractRStarTree<?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { + public GenericRStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { super(distanceQuery); this.tree = tree; this.distanceFunction = distanceQuery.getDistanceFunction(); @@ -104,32 +102,33 @@ 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() << 1, 20)); + final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq = new ComparableMinHeap<>(Math.min(knnList.getK() << 1, 20)); + tree.statistics.countKNNQuery(); // push root - pq.add(new GenericDistanceSearchCandidate<D>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); + pq.add(new GenericDistanceSearchCandidate<>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); D maxDist = distanceFunction.getDistanceFactory().infiniteDistance(); // search in tree - while(!pq.isEmpty()) { + while (!pq.isEmpty()) { GenericDistanceSearchCandidate<D> pqNode = pq.poll(); - if(pqNode.mindist.compareTo(maxDist) > 0) { + if (pqNode.mindist.compareTo(maxDist) > 0) { return; } maxDist = expandNode(object, knnList, pq, maxDist, pqNode.nodeID); } } - private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { + private D expandNode(O object, KNNHeap<D> knnList, final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { + if (node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); D distance = distanceFunction.minDist(entry, object); - tree.distanceCalcs++; - if(distance.compareTo(maxDist) <= 0) { + tree.statistics.countDistanceCalculation(); + if (distance.compareTo(maxDist) <= 0) { knnList.add(distance, ((LeafEntry) entry).getDBID()); maxDist = knnList.getKNNDistance(); } @@ -137,17 +136,16 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } // directory node else { - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); D distance = distanceFunction.minDist(entry, object); - tree.distanceCalcs++; + tree.statistics.countDistanceCalculation(); // Greedy expand, bypassing the queue - if(distance.isNullDistance()) { + if (distance.isNullDistance()) { expandNode(object, knnList, pq, maxDist, ((DirectoryEntry) entry).getPageID()); - } - else { - if(distance.compareTo(maxDist) <= 0) { - pq.add(new GenericDistanceSearchCandidate<D>(distance, ((DirectoryEntry) entry).getPageID())); + } else { + if (distance.compareTo(maxDist) <= 0) { + pq.add(new GenericDistanceSearchCandidate<>(distance, ((DirectoryEntry) entry).getPageID())); } } } @@ -162,10 +160,10 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param knnLists a map containing the knn lists for each query objects */ protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap<D>> knnLists) { - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { + if (node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { SpatialEntry p = node.getEntry(i); - for(Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { + for (Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { final DBID q = ent.getKey(); final KNNHeap<D> knns_q = ent.getValue(); D knn_q_maxDist = knns_q.getKNNDistance(); @@ -173,26 +171,26 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis DBID pid = ((LeafEntry) p).getDBID(); // FIXME: objects are NOT accessible by DBID in a plain rtree context! D dist_pq = distanceQuery.distance(pid, q); - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { + tree.statistics.countDistanceCalculation(); + if (dist_pq.compareTo(knn_q_maxDist) <= 0) { knns_q.add(dist_pq, pid); } } } - } - else { + } else { ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size()); - for(DBID id : knnLists.keySet()) { + for (DBID id : knnLists.keySet()) { ids.add(id); } - List<DistanceEntry<D, SpatialEntry>> entries = getSortedEntries(node, ids); - for(DistanceEntry<D, SpatialEntry> distEntry : entries) { - D minDist = distEntry.getDistance(); - for(Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { + List<FCPair<D, SpatialEntry>> entries = getSortedEntries(node, ids); + for (FCPair<D, SpatialEntry> distEntry : entries) { + D minDist = distEntry.first; + for (Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { final KNNHeap<D> knns_q = ent.getValue(); D knn_q_maxDist = knns_q.getKNNDistance(); - if(minDist.compareTo(knn_q_maxDist) <= 0) { - SpatialEntry entry = distEntry.getEntry(); + if (minDist.compareTo(knn_q_maxDist) <= 0) { + SpatialEntry entry = distEntry.second; AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; @@ -210,17 +208,18 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param ids the id of the objects * @return a list of the sorted entries */ - protected List<DistanceEntry<D, SpatialEntry>> getSortedEntries(AbstractRStarTreeNode<?, ?> node, DBIDs ids) { - List<DistanceEntry<D, SpatialEntry>> result = new ArrayList<DistanceEntry<D, SpatialEntry>>(); + protected List<FCPair<D, SpatialEntry>> getSortedEntries(AbstractRStarTreeNode<?, ?> node, DBIDs ids) { + List<FCPair<D, SpatialEntry>> result = new ArrayList<>(); - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { SpatialEntry entry = node.getEntry(i); D minMinDist = distanceQuery.getDistanceFactory().infiniteDistance(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { D minDist = distanceFunction.minDist(entry, relation.get(iter)); + tree.statistics.countDistanceCalculation(); minMinDist = DistanceUtil.min(minDist, minMinDist); } - result.add(new DistanceEntry<D, SpatialEntry>(entry, minMinDist, i)); + result.add(new FCPair<>(minMinDist, entry)); } Collections.sort(result); @@ -228,38 +227,27 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } @Override - public KNNResult<D> getKNNForObject(O obj, int k) { - if(k < 1) { - throw new IllegalArgumentException("At least one enumeration has to be requested!"); - } - - final KNNHeap<D> knnList = KNNUtil.newHeap(distanceFunction, k); + public KNNList<D> getKNNForObject(O obj, int k) { + final KNNHeap<D> knnList = DBIDUtil.newHeap(distanceFunction.getDistanceFactory(), k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @Override - public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { - return getKNNForObject(relation.get(id), k); - } - - @Override - public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { - if(k < 1) { - throw new IllegalArgumentException("At least one enumeration has to be requested!"); - } + public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { // 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()); + final Map<DBID, KNNHeap<D>> knnLists = new HashMap<>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - knnLists.put(DBIDUtil.deref(iter), KNNUtil.newHeap(distanceFunction, k)); + knnLists.put(DBIDUtil.deref(iter), DBIDUtil.newHeap(distanceFunction.getDistanceFactory(), k)); } batchNN(tree.getRoot(), knnLists); - List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(); + List<KNNList<D>> result = new ArrayList<>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + tree.statistics.countKNNQuery(); result.add(knnLists.get(DBIDUtil.deref(iter)).toKNNList()); } return result; } -}
\ No newline at end of file +} 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 a5232b30..16a3393a 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,19 +24,18 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; */ 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.ids.distance.DistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; 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; import de.lmu.ifi.dbs.elki.index.tree.query.GenericDistanceSearchCandidate; 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.ComparableMinHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -60,7 +59,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D /** * The index to use */ - protected final AbstractRStarTree<?, ?> tree; + protected final AbstractRStarTree<?, ?, ?> tree; /** * Spatial primitive distance function @@ -73,7 +72,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param tree Index to use * @param distanceQuery Distance query to use */ - public GenericRStarTreeRangeQuery(AbstractRStarTree<?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { + public GenericRStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { super(distanceQuery); this.tree = tree; this.distanceFunction = distanceQuery.getDistanceFunction(); @@ -86,12 +85,13 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param epsilon Query range * @return Objects contained in query range. */ - protected DistanceDBIDResult<D> doRangeQuery(O object, D epsilon) { - final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); - final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(); + protected DistanceDBIDList<D> doRangeQuery(O object, D epsilon) { + final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); + final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq = new ComparableMinHeap<>(); + tree.statistics.countRangeQuery(); // push root - pq.add(new GenericDistanceSearchCandidate<D>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); + pq.add(new GenericDistanceSearchCandidate<>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); // search in tree while(!pq.isEmpty()) { @@ -100,11 +100,12 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { D distance = distanceFunction.minDist(node.getEntry(i), object); + tree.statistics.countDistanceCalculation(); if(distance.compareTo(epsilon) <= 0) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); @@ -112,7 +113,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); - pq.add(new GenericDistanceSearchCandidate<D>(distance, entry.getEntryID())); + pq.add(new GenericDistanceSearchCandidate<>(distance, entry.getEntryID())); } } } @@ -124,12 +125,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } @Override - public DistanceDBIDResult<D> getRangeForObject(O obj, D range) { + public DistanceDBIDList<D> getRangeForObject(O obj, D range) { return doRangeQuery(obj, range); } - - @Override - public DistanceDBIDResult<D> getRangeForDBID(DBIDRef id, D range) { - return getRangeForObject(relation.get(id), range); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java index 477e3a36..46c814ee 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -62,17 +62,17 @@ public final class RStarTreeUtil { * @return Query object */ @SuppressWarnings({ "cast", "unchecked" }) - public static <O extends SpatialComparable, D extends Distance<D>> RangeQuery<O, D> getRangeQuery(AbstractRStarTree<?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { + public static <O extends SpatialComparable, D extends Distance<D>> RangeQuery<O, D> getRangeQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { // Can we support this distance function - spatial distances only! SpatialPrimitiveDistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); // Can we use an optimized query? if(df instanceof SpatialPrimitiveDoubleDistanceFunction) { DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) DistanceQuery.class.cast(distanceQuery); SpatialPrimitiveDoubleDistanceFunction<? super O> dfc = (SpatialPrimitiveDoubleDistanceFunction<? super O>) SpatialPrimitiveDoubleDistanceFunction.class.cast(df); - RangeQuery<O, ?> q = new DoubleDistanceRStarTreeRangeQuery<O>(tree, dqc, dfc); + RangeQuery<O, ?> q = new DoubleDistanceRStarTreeRangeQuery<>(tree, dqc, dfc); return (RangeQuery<O, D>) q; } - return new GenericRStarTreeRangeQuery<O, D>(tree, distanceQuery); + return new GenericRStarTreeRangeQuery<>(tree, distanceQuery); } /** @@ -87,16 +87,16 @@ public final class RStarTreeUtil { * @return Query object */ @SuppressWarnings({ "cast", "unchecked" }) - public static <O extends SpatialComparable, D extends Distance<D>> KNNQuery<O, D> getKNNQuery(AbstractRStarTree<?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { + public static <O extends SpatialComparable, D extends Distance<D>> KNNQuery<O, D> getKNNQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { // Can we support this distance function - spatial distances only! SpatialPrimitiveDistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); // Can we use an optimized query? if(df instanceof SpatialPrimitiveDoubleDistanceFunction) { DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) DistanceQuery.class.cast(distanceQuery); SpatialPrimitiveDoubleDistanceFunction<? super O> dfc = (SpatialPrimitiveDoubleDistanceFunction<? super O>) SpatialPrimitiveDoubleDistanceFunction.class.cast(df); - KNNQuery<O, ?> q = new DoubleDistanceRStarTreeKNNQuery<O>(tree, dqc, dfc); + KNNQuery<O, ?> q = new DoubleDistanceRStarTreeKNNQuery<>(tree, dqc, dfc); return (KNNQuery<O, D>) q; } - return new GenericRStarTreeKNNQuery<O, D>(tree, distanceQuery); + return new GenericRStarTreeKNNQuery<>(tree, distanceQuery); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java index 0b47cab0..69bcd3d0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 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/spatial/rstarvariants/rstar/RStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java index d63d77cb..1c2a7fe8 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,6 +25,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -44,7 +45,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title; @Title("R*-Tree") @Description("Balanced index structure based on bounding rectangles.") @Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", title = "The R*-tree: an efficient and robust access method for points and rectangles", booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", url = "http://dx.doi.org/10.1145/93597.98741") -public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { +public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry, AbstractRTreeSettings> { /** * The logger for this class. */ @@ -54,9 +55,10 @@ public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { * Constructor. * * @param pagefile Page file + * @param settings Settings class */ - public RStarTree(PageFile<RStarTreeNode> pagefile) { - super(pagefile); + public RStarTree(PageFile<RStarTreeNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); } @Override 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 da7c03fd..72f7f7dd 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,11 +27,10 @@ import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeFactory; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.BulkSplit; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.InsertionStrategy; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.OverflowTreatment; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.SplitStrategy; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; +import de.lmu.ifi.dbs.elki.utilities.Alias; /** * Factory for regular R*-Trees. @@ -43,33 +42,22 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>> { +@Alias({"rstar", "r*"}) +public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>, AbstractRTreeSettings> { /** * Constructor. * - * @param fileName - * @param pageSize - * @param cacheSize - * @param bulkSplitter Bulk loading strategy - * @param insertionStrategy the strategy to find the insertion child - * @param nodeSplitter the strategy for splitting nodes. - * @param overflowTreatment the strategy to use for overflow treatment - * @param minimumFill the relative minimum fill + * @param pageFileFactory Data storage + * @param settings Tree settings */ - public RStarTreeFactory(String fileName, int pageSize, long cacheSize, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy, SplitStrategy nodeSplitter, OverflowTreatment overflowTreatment, double minimumFill) { - super(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); + public RStarTreeFactory(PageFileFactory<?> pageFileFactory, AbstractRTreeSettings settings) { + super(pageFileFactory, settings); } @Override public RStarTreeIndex<O> instantiate(Relation<O> relation) { PageFile<RStarTreeNode> pagefile = makePageFile(getNodeClass()); - RStarTreeIndex<O> index = new RStarTreeIndex<O>(relation, pagefile); - index.setBulkStrategy(bulkSplitter); - index.setInsertionStrategy(insertionStrategy); - index.setNodeSplitStrategy(nodeSplitter); - index.setOverflowTreatment(overflowTreatment); - index.setMinimumFill(minimumFill); - return index; + return new RStarTreeIndex<>(relation, pagefile, settings); } protected Class<RStarTreeNode> getNodeClass() { @@ -82,11 +70,18 @@ public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTr * @author Erich Schubert * * @apiviz.exclude + * + * @param <O> Object type */ - public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { @Override protected RStarTreeFactory<O> makeInstance() { - return new RStarTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); + return new RStarTreeFactory<>(pageFileFactory, settings); + } + + @Override + protected AbstractRTreeSettings createSettings() { + return new AbstractRTreeSettings(); } } }
\ No newline at end of file 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 1946293f..15b43e64 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -37,11 +37,13 @@ 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.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; @@ -53,7 +55,7 @@ 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>, DynamicIndex { /** * The appropriate logger for this index. */ @@ -69,11 +71,11 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme * * @param relation Relation to index * @param pagefile Page file + * @param settings Tree settings */ - public RStarTreeIndex(Relation<O> relation, PageFile<RStarTreeNode> pagefile) { - super(pagefile); + public RStarTreeIndex(Relation<O> relation, PageFile<RStarTreeNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); this.relation = relation; - this.initialize(); } /** @@ -86,6 +88,12 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme return new SpatialPointLeafEntry(DBIDUtil.deref(id), relation.get(id)); } + @Override + public void initialize() { + super.initialize(); + insertAll(relation.getDBIDs()); // Will check for actual bulk load! + } + /** * Inserts the specified reel vector object into this index. * @@ -110,7 +118,7 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme // Make an example leaf if(canBulkLoad()) { - List<SpatialEntry> leafs = new ArrayList<SpatialEntry>(ids.size()); + List<SpatialEntry> leafs = new ArrayList<>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { leafs.add(createNewLeafEntry(iter)); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java index b51d191a..7226fa1c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/rstar/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java index e15569c5..7897fae1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 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/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java index 4a0304f1..7d463a03 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java @@ -7,7 +7,7 @@ import java.util.List; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -75,7 +75,7 @@ public abstract class AbstractBulkSplit implements BulkSplit { // build partitions final int size = objects.size(); final int numberPartitions = (int) Math.ceil(((double) size) / maxEntries); - List<List<T>> partitions = new ArrayList<List<T>>(numberPartitions); + List<List<T>> partitions = new ArrayList<>(numberPartitions); int start = 0; for(int pnum = 0; pnum < numberPartitions; pnum++) { int end = (int) ((pnum + 1.) * size / numberPartitions); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java new file mode 100644 index 00000000..fbbf7d8f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java @@ -0,0 +1,151 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; + +/* + 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 java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMeanComparator; +import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * This is variation of the original STR bulk load for non-rectangular data + * spaces. Instead of iterating through the dimensions and splitting each by + * (approximately) the same factor, this variation tries to adjust the factor to + * the extends of the data space. I.e. if the data set is twice as wide as high, + * this should produce twice as many partitions on the X than on the Y axis. + * + * Whether or not this offers benefits greatly depends on the distance queries + * used. But for symmetric distances, the resulting pages should be more + * rectangular, which often is beneficial. + * + * See {@link SortTileRecursiveBulkSplit} for the original STR bulk load. + * + * @author Erich Schubert + */ +public class AdaptiveSortTileRecursiveBulkSplit extends AbstractBulkSplit { + /** + * Static instance. + */ + public static final AdaptiveSortTileRecursiveBulkSplit STATIC = new AdaptiveSortTileRecursiveBulkSplit(); + + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + final int dims = spatialObjects.get(0).getDimensionality(); + final int p = (int) Math.ceil(spatialObjects.size() / (double) maxEntries); + List<List<T>> ret = new ArrayList<>(p); + strPartition(spatialObjects, 0, spatialObjects.size(), 0, dims, maxEntries, new SpatialSingleMeanComparator(0), ret); + return ret; + } + + /** + * Recursively partition. + * + * @param objs Object list + * @param start Subinterval start + * @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, SpatialSingleMeanComparator c, List<List<T>> ret) { + final int p = (int) Math.ceil((end - start) / (double) maxEntries); + + // Compute min and max: + double[] mm = new double[dims * 2]; + for (int d = 0; d < mm.length; d += 2) { + mm[d] = Double.POSITIVE_INFINITY; // min <- +inf + mm[d + 1] = Double.NEGATIVE_INFINITY; // max <- -inf + } + for (int i = start; i < end; i++) { + T o = objs.get(i); + for (int d1 = 0, d2 = 0; d2 < mm.length; d1++, d2 += 2) { + mm[d2] = Math.min(mm[d2], o.getMin(d1)); + mm[d2 + 1] = Math.max(mm[d2 + 1], o.getMax(d1)); + } + } + // Find maximum and compute extends + double maxex = 0.0; + int sdim = depth; + double[] exts = new double[dims]; + for (int d = 0; d < mm.length; d += 2) { + final double extend = mm[d + 1] - mm[d]; + if (extend > maxex) { + maxex = extend; + sdim = d >>> 1; + } + exts[d >>> 1] = extend; + } + // Compute sum of the k largest extends: + Arrays.sort(exts); + double extsum = 0.; + for (int d = depth; d < exts.length; d++) { + extsum += exts[d]; + } + // Chose the number of partitions: + final int s; + if (maxex > 0. && depth + 1 < dims) { + s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth)) * (dims - depth) * maxex / extsum); + } else { + s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); + } + + final double len = end - start; // double intentional! + for (int i = 0; i < s; i++) { + // We don't completely sort, but only ensure the quantile is invariant. + int s2 = start + (int) ((i * len) / s); + int e2 = start + (int) (((i + 1) * len) / s); + // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); + if (e2 < end) { + c.setDimension(sdim); + QuickSelect.quickSelect(objs, c, s2, end, e2); + } + if (depth + 1 == dims) { + ret.add(objs.subList(s2, e2)); + } else { + // Descend + strPartition(objs, s2, e2, depth + 1, dims, maxEntries, c, ret); + } + } + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected AdaptiveSortTileRecursiveBulkSplit makeInstance() { + return STATIC; + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java index 1eb88f7c..c32a512c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java index 308c70cb..8b0dfd77 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java index 2fd69531..5251e18b 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,7 +29,7 @@ import java.util.Collections; import java.util.List; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util.SpatialComparator; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMinComparator; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @@ -39,14 +39,14 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * * @author Elke Achtert * - * @apiviz.uses SpatialComparator + * @apiviz.composedOf SpatialSingleMinComparator */ public class MaxExtensionBulkSplit extends AbstractBulkSplit { /** * Logger. */ private static final Logging LOG = Logging.getLogger(MaxExtensionBulkSplit.class); - + /** * Static instance */ @@ -70,40 +70,40 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { */ @Override public <N extends SpatialComparable> List<List<N>> partition(List<N> spatialObjects, int minEntries, int maxEntries) { - List<List<N>> partitions = new ArrayList<List<N>>(); - List<N> objects = new ArrayList<N>(spatialObjects); + List<List<N>> partitions = new ArrayList<>(); + List<N> objects = new ArrayList<>(spatialObjects); - while(objects.size() > 0) { + while (objects.size() > 0) { StringBuilder msg = new StringBuilder(); // get the split axis and split point int splitAxis = chooseMaximalExtendedSplitAxis(objects); int splitPoint = chooseBulkSplitPoint(objects.size(), minEntries, maxEntries); - if(LOG.isDebugging()) { + if (LOG.isDebugging()) { msg.append("\nsplitAxis ").append(splitAxis); msg.append("\nsplitPoint ").append(splitPoint); } // sort in the right dimension - Collections.sort(objects, new SpatialComparator(splitAxis, SpatialComparator.MIN)); + Collections.sort(objects, new SpatialSingleMinComparator(splitAxis)); // insert into partition - List<N> partition1 = new ArrayList<N>(); - for(int i = 0; i < splitPoint; i++) { + List<N> partition1 = new ArrayList<>(); + for (int i = 0; i < splitPoint; i++) { N o = objects.remove(0); partition1.add(o); } partitions.add(partition1); // copy array - if(LOG.isDebugging()) { + if (LOG.isDebugging()) { msg.append("\ncurrent partition ").append(partition1); msg.append("\nremaining objects # ").append(objects.size()); LOG.debugFine(msg.toString()); } } - if(LOG.isDebugging()) { + if (LOG.isDebugging()) { LOG.debugFine("partitions " + partitions); } return partitions; @@ -124,17 +124,17 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { Arrays.fill(minExtension, Double.MAX_VALUE); // compute min and max value in each dimension - for(SpatialComparable object : objects) { - for(int d = 0; d < dimension; d++) { + for (SpatialComparable object : objects) { + for (int d = 0; d < dimension; d++) { double min, max; min = object.getMin(d); max = object.getMax(d); - if(maxExtension[d] < max) { + if (maxExtension[d] < max) { maxExtension[d] = max; } - if(minExtension[d] > min) { + if (minExtension[d] > min) { minExtension[d] = min; } } @@ -143,9 +143,9 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { // set split axis to dim with maximal extension int splitAxis = -1; double max = 0; - for(int d = 0; d < dimension; d++) { + for (int d = 0; d < dimension; d++) { double currentExtension = maxExtension[d] - minExtension[d]; - if(max < currentExtension) { + if (max < currentExtension) { max = currentExtension; splitAxis = d; } @@ -166,4 +166,4 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { return MaxExtensionBulkSplit.STATIC; } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java new file mode 100644 index 00000000..6bf37642 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java @@ -0,0 +1,134 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; + +/* + 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 java.util.ArrayList; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMeanComparator; +import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * This is variation of the {@link SortTileRecursiveBulkSplit}, incorporating + * some ideas from {@link MaxExtensionBulkSplit}. Instead of iterating through + * the axes in order, it always chooses the axis with the largest extend. This + * may rarely lead to the data being split on the same axis twice, but most + * importantly it varies the splitting order compared to STR. + * + * {@link AdaptiveSortTileRecursiveBulkSplit} takes these ideas one step + * further, by also varying the fan-out degree. + * + * @author Erich Schubert + */ +public class MaxExtensionSortTileRecursiveBulkSplit extends AbstractBulkSplit { + /** + * Static instance. + */ + public static final MaxExtensionSortTileRecursiveBulkSplit STATIC = new MaxExtensionSortTileRecursiveBulkSplit(); + + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + final int dims = spatialObjects.get(0).getDimensionality(); + final int p = (int) Math.ceil(spatialObjects.size() / (double) maxEntries); + List<List<T>> ret = new ArrayList<>(p); + strPartition(spatialObjects, 0, spatialObjects.size(), 0, dims, maxEntries, new SpatialSingleMeanComparator(0), ret); + return ret; + } + + /** + * Recursively partition. + * + * @param objs Object list + * @param start Subinterval start + * @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, SpatialSingleMeanComparator c, List<List<T>> ret) { + final int p = (int) Math.ceil((end - start) / (double) maxEntries); + + // Compute min and max: + double[] mm = new double[dims * 2]; + for (int d = 0; d < mm.length; d += 2) { + mm[d] = Double.POSITIVE_INFINITY; // min <- +inf + mm[d + 1] = Double.NEGATIVE_INFINITY; // max <- -inf + } + for (int i = start; i < end; i++) { + T o = objs.get(i); + for (int d1 = 0, d2 = 0; d2 < mm.length; d1++, d2 += 2) { + mm[d2] = Math.min(mm[d2], o.getMin(d1)); + mm[d2 + 1] = Math.max(mm[d2 + 1], o.getMax(d1)); + } + } + // Find maximum and compute extends + double maxex = 0.0; + int sdim = -1; + for (int d = 0; d < mm.length; d += 2) { + final double extend = mm[d + 1] - mm[d]; + if (extend > maxex) { + maxex = extend; + sdim = d >> 1; + } + } + // Chose the number of partitions: + final int s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); + + final double len = end - start; // double intentional! + for (int i = 0; i < s; i++) { + // We don't completely sort, but only ensure the quantile is invariant. + int s2 = start + (int) ((i * len) / s); + int e2 = start + (int) (((i + 1) * len) / s); + // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); + if (e2 < end) { + c.setDimension(sdim); + QuickSelect.quickSelect(objs, c, s2, end, e2); + } + if (depth + 1 == dims) { + ret.add(objs.subList(s2, e2)); + } else { + // Descend + strPartition(objs, s2, e2, depth + 1, dims, maxEntries, c, ret); + } + } + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected MaxExtensionSortTileRecursiveBulkSplit makeInstance() { + return STATIC; + } + } +} 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 2209ddef..5d2083b3 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,10 +23,10 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; along with this program. If not, see <http://www.gnu.org/licenses/>. */ import java.util.Collections; -import java.util.Comparator; import java.util.List; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMeanComparator; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @@ -47,7 +47,7 @@ public class OneDimSortBulkSplit extends AbstractBulkSplit { /** * Static instance. */ - public static final AbstractBulkSplit STATIC = new OneDimSortBulkSplit(); + public static final OneDimSortBulkSplit STATIC = new OneDimSortBulkSplit(); /** * Constructor. @@ -59,14 +59,7 @@ public class OneDimSortBulkSplit extends AbstractBulkSplit { @Override public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { // Sort by first dimension - Collections.sort(spatialObjects, new Comparator<SpatialComparable>() { - @Override - public int compare(SpatialComparable o1, SpatialComparable o2) { - double min1 = (o1.getMax(0) + o1.getMin(0)) * .5; - double min2 = (o2.getMax(0) + o2.getMin(0)) * .5; - return Double.compare(min1, min2); - } - }); + Collections.sort(spatialObjects, new SpatialSingleMeanComparator(0)); return trivialPartition(spatialObjects, minEntries, maxEntries); } @@ -79,8 +72,8 @@ public class OneDimSortBulkSplit extends AbstractBulkSplit { */ public static class Parameterizer extends AbstractParameterizer { @Override - protected AbstractBulkSplit makeInstance() { + protected OneDimSortBulkSplit makeInstance() { return OneDimSortBulkSplit.STATIC; } } -}
\ No newline at end of file +} 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 e24ef3ce..6cd7a598 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,12 +23,14 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; along with this program. If not, see <http://www.gnu.org/licenses/>. */ import java.util.ArrayList; -import java.util.Comparator; import java.util.List; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMeanComparator; +import de.lmu.ifi.dbs.elki.utilities.Alias; import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** * Sort-Tile-Recursive aims at tiling the data space with a grid-like structure @@ -44,13 +46,19 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Erich Schubert */ @Reference(authors = "Leutenegger, S.T. and Lopez, M.A. and Edgington, J.", title = "STR: A simple and efficient algorithm for R-tree packing", booktitle = "Proc. 13th International Conference on Data Engineering, 1997", url = "http://dx.doi.org/10.1109/ICDE.1997.582015") +@Alias({"str", "STR"}) public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { + /** + * Static instance. + */ + public static final SortTileRecursiveBulkSplit STATIC = new SortTileRecursiveBulkSplit(); + @Override public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { final int dims = spatialObjects.get(0).getDimensionality(); final int p = (int) Math.ceil(spatialObjects.size() / (double) maxEntries); - List<List<T>> ret = new ArrayList<List<T>>(p); - strPartition(spatialObjects, 0, spatialObjects.size(), 0, dims, maxEntries, new Compare<T>(), ret); + List<List<T>> ret = new ArrayList<>(p); + strPartition(spatialObjects, 0, spatialObjects.size(), 0, dims, maxEntries, new SpatialSingleMeanComparator(0), ret); return ret; } @@ -67,24 +75,23 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { * @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) { + protected <T extends SpatialComparable> void strPartition(List<T> objs, int start, int end, int depth, int dims, int maxEntries, SpatialSingleMeanComparator c, List<List<T>> ret) { final int p = (int) Math.ceil((end - start) / (double) maxEntries); final int s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); final double len = end - start; // double intentional! - for(int i = 0; i < s; i++) { + for (int i = 0; i < s; i++) { // We don't completely sort, but only ensure the quantile is invariant. int s2 = start + (int) ((i * len) / s); int e2 = start + (int) (((i + 1) * len) / s); // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); - if(e2 < end) { - c.dim = depth; + if (e2 < end) { + c.setDimension(depth); QuickSelect.quickSelect(objs, c, s2, end, e2); } - if(depth + 1 == dims) { + if (depth + 1 == dims) { ret.add(objs.subList(s2, e2)); - } - else { + } else { // Descend strPartition(objs, s2, e2, depth + 1, dims, maxEntries, c, ret); } @@ -92,25 +99,16 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { } /** - * Comparison helper. - * - * @apiviz.exclude + * Parameterization class. * * @author Erich Schubert * - * @param <T> Type + * @apiviz.exclude */ - private static class Compare<T extends SpatialComparable> implements Comparator<T> { - /** - * Current dimension. - */ - int dim; - + public static class Parameterizer extends AbstractParameterizer { @Override - public int compare(T o1, T o2) { - final double v1 = o1.getMin(dim) + o1.getMax(dim); - final double v2 = o2.getMin(dim) + o2.getMax(dim); - return Double.compare(v1, v2); + protected SortTileRecursiveBulkSplit makeInstance() { + return STATIC; } } -}
\ No newline at end of file +} 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 beb6e657..6e2b6369 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -40,7 +40,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * <p> * On packing R-trees<br/> * Kamel, I. and Faloutsos, C.<br/> - * Proc. 2of the second international conference on Information and knowledge + * Proc. of the second international conference on Information and knowledge * management * </p> * @@ -48,7 +48,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * * @author Erich Schubert */ -@Reference(title = "On packing R-trees", authors = "Kamel, I. and Faloutsos, C.", booktitle = "Proc. 2of the second international conference on Information and knowledge management", url = "http://dx.doi.org/10.1145/170088.170403") +@Reference(title = "On packing R-trees", authors = "Kamel, I. and Faloutsos, C.", booktitle = "Proc. of the second international conference on Information and knowledge management", url = "http://dx.doi.org/10.1145/170088.170403") public class SpatialSortBulkSplit extends AbstractBulkSplit { /** * Sorting class @@ -93,7 +93,7 @@ public class SpatialSortBulkSplit extends AbstractBulkSplit { protected void makeOptions(Parameterization config) { super.makeOptions(config); - ObjectParameter<SpatialSorter> sorterP = new ObjectParameter<SpatialSorter>(SORTER_ID, SpatialSorter.class); + ObjectParameter<SpatialSorter> sorterP = new ObjectParameter<>(SORTER_ID, SpatialSorter.class); if(config.grab(sorterP)) { sorter = sorterP.instantiateClass(config); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java index 0d01ba83..5c52de3e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 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/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java index c39bd914..5b4e7a56 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 @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -77,7 +77,7 @@ public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInse } // Heap of candidates - TopBoundedHeap<DoubleIntPair> candidates = new TopBoundedHeap<DoubleIntPair>(numCandidates, Collections.reverseOrder()); + TopBoundedHeap<DoubleIntPair> candidates = new TopBoundedHeap<>(numCandidates, Collections.reverseOrder()); for(int i = 0; i < size; i++) { // Existing object and extended rectangle: SpatialComparable entry = getter.get(options, i); 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 63bbe9dc..837f0312 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 @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -108,12 +108,12 @@ public class CombinedInsertionStrategy implements InsertionStrategy { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - ClassParameter<InsertionStrategy> dirP = new ClassParameter<InsertionStrategy>(DIR_STRATEGY_ID, InsertionStrategy.class, LeastEnlargementWithAreaInsertionStrategy.class); + ClassParameter<InsertionStrategy> dirP = new ClassParameter<>(DIR_STRATEGY_ID, InsertionStrategy.class, LeastEnlargementWithAreaInsertionStrategy.class); if(config.grab(dirP)) { dirStrategy = dirP.instantiateClass(config); } - ClassParameter<InsertionStrategy> leafP = new ClassParameter<InsertionStrategy>(LEAF_STRATEGY_ID, InsertionStrategy.class, LeastOverlapInsertionStrategy.class); + ClassParameter<InsertionStrategy> leafP = new ClassParameter<>(LEAF_STRATEGY_ID, InsertionStrategy.class, LeastOverlapInsertionStrategy.class); if(config.grab(leafP)) { leafStrategy = leafP.instantiateClass(config); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java index 96294514..477f0f48 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java index eb211cb6..39348bf5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java index 977a132b..627428e9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java index 2eba8912..18855d90 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/insert/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java index ad54e1e1..d425c7bd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/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) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java index 3c25cbbc..0af90d78 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,7 +25,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow import java.util.BitSet; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SquaredEuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; @@ -73,7 +73,7 @@ public class LimitedReinsertOverflowTreatment implements OverflowTreatment { } @Override - public <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E> tree, N node, IndexTreePath<E> path) { + public <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E, ?> tree, N node, IndexTreePath<E> path) { final int level = /* tree.getHeight() - */(path.getPathCount() - 1); // No reinsertions at root level if(path.getPathCount() == 1) { @@ -121,7 +121,7 @@ public class LimitedReinsertOverflowTreatment implements OverflowTreatment { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - ObjectParameter<ReinsertStrategy> strategyP = new ObjectParameter<ReinsertStrategy>(REINSERT_STRATEGY_ID, ReinsertStrategy.class, CloseReinsert.class); + ObjectParameter<ReinsertStrategy> strategyP = new ObjectParameter<>(REINSERT_STRATEGY_ID, ReinsertStrategy.class, CloseReinsert.class); if(config.grab(strategyP)) { reinsertStrategy = strategyP.instantiateClass(config); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java index 87d09038..4b2f94b1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -49,5 +49,5 @@ public interface OverflowTreatment { * @param path Path * @return true when already handled (e.g. by reinserting) */ - <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E> tree, N node, IndexTreePath<E> path); + <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E, ?> tree, N node, IndexTreePath<E> path); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java index cfbcf6a9..82ceb4ef 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -48,7 +48,7 @@ public class SplitOnlyOverflowTreatment implements OverflowTreatment { } @Override - public <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E> tree, N node, IndexTreePath<E> path) { + public <N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry> boolean handleOverflow(AbstractRStarTree<N, E, ?> tree, N node, IndexTreePath<E> path) { return false; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java index 30899736..fc7f16f0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java index 41e2eb0b..7d2dfc0a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/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) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java index bb222dfe..cf447985 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert */ import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SquaredEuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.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.GreaterConstraint; @@ -99,7 +99,7 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { if (config.grab(reinsertAmountP)) { reinsertAmount = reinsertAmountP.getValue(); } - ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); + ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); if (config.grab(distanceP)) { distanceFunction = distanceP.instantiateClass(config); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java index 12a4ed0f..3002f18b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java @@ -15,7 +15,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/reinsert/FarReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java index 771f56fb..02c1d4d7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java @@ -15,7 +15,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java index cba96367..2a4f130f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/reinsert/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java index f6a6f6e9..2d2c6871 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java index 3e3d599c..c31abc2d 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/GreeneSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java index 99c15fd6..d00479cf 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java index b4ff2364..4dc9b15d 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java index 8f61771d..91ef8f16 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/SplitStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java index 658a63da..0bc1ffcf 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/strategies/split/TopologicalSplitter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java index ab32ba19..dc9092ad 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 @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -50,7 +50,7 @@ public class TopologicalSplitter implements SplitStrategy { public static final TopologicalSplitter STATIC = new TopologicalSplitter(); /** - * constructor. + * Constructor. */ public TopologicalSplitter() { // Nothing to do. @@ -58,7 +58,7 @@ public class TopologicalSplitter implements SplitStrategy { @Override public <E extends SpatialComparable, A> BitSet split(A entries, ArrayAdapter<E, A> getter, int minEntries) { - Split<A, E> split = new Split<A, E>(entries, getter); + Split<A, E> split = new Split<>(entries, getter); split.chooseSplitAxis(minEntries); split.chooseSplitPoint(minEntries); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java index 9e8291be..bb8cb1e2 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/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) 2012 + Copyright (C) 2013 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/spatial/rstarvariants/util/NodeArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java index 3bf35d9d..def824ba 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -43,7 +43,6 @@ public class NodeArrayAdapter implements ArrayAdapter<SpatialEntry, AbstractNode */ protected NodeArrayAdapter() { super(); - // TODO Auto-generated constructor stub } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/SpatialComparator.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/SpatialComparator.java deleted file mode 100644 index 2f1ea9b1..00000000 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/SpatialComparator.java +++ /dev/null @@ -1,103 +0,0 @@ -package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2012 - 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 java.util.Comparator; - -import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; - -/** - * Compares objects of type SpatialComparable. - * - * @author Elke Achtert - * - * @apiviz.uses SpatialComparable - */ -public final class SpatialComparator implements Comparator<SpatialComparable> { - /** - * Indicates the comparison of the min values of the entries' MBRs. - */ - public static final int MIN = 1; - - /** - * Indicates the comparison of the max values of the entries' MBRs. - */ - public static final int MAX = 2; - - /** - * The dimension for comparison. - */ - private final int compareDimension; - - /** - * Indicates the comparison value (min or max). - */ - private final int comparisonValue; - - /** - * Creates a new spatial comparator with the specified parameters. - * - * @param compareDimension the dimension to be set for comparison - * @param comparisonValue the comparison value to be set - */ - public SpatialComparator(int compareDimension, int comparisonValue) { - this.compareDimension = compareDimension; - this.comparisonValue = comparisonValue; - } - - /** - * Compares the two specified spatial comparables according to the sorting - * dimension and the comparison value of this Comparator. - * - * @param o1 the first spatial comparable - * @param o2 the second spatial comparable - * @return a negative integer, zero, or a positive integer as the first - * argument is less than, equal to, or greater than the second. - */ - @Override - public int compare(SpatialComparable o1, SpatialComparable o2) { - if(comparisonValue == MIN) { - if(o1.getMin(compareDimension) < o2.getMin(compareDimension)) { - return -1; - } - - if(o1.getMin(compareDimension) > o2.getMin(compareDimension)) { - return +1; - } - } - else if(comparisonValue == MAX) { - if(o1.getMax(compareDimension) < o2.getMax(compareDimension)) { - return -1; - } - - if(o1.getMax(compareDimension) > o2.getMax(compareDimension)) { - return +1; - } - } - else { - throw new IllegalArgumentException("No comparison value specified!"); - } - return 0; - } -} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java index 10991028..22088417 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java @@ -6,7 +6,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2012 +Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |