diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree')
64 files changed, 1280 insertions, 1072 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/AbstractLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/AbstractLeafEntry.java index d2d38976..ea5fd6de 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/AbstractLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/AbstractLeafEntry.java @@ -74,7 +74,7 @@ public abstract class AbstractLeafEntry implements LeafEntry { */ @Override public void writeExternal(ObjectOutput out) throws IOException { - out.writeInt(id.getIntegerID()); + out.writeInt(DBIDUtil.asInteger(id)); } /** diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/AbstractNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/AbstractNode.java index 42f4fa11..4f2c6d04 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/AbstractNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/AbstractNode.java @@ -341,7 +341,7 @@ public abstract class AbstractNode<E extends Entry> extends AbstractExternalizab public final void splitTo(AbstractNode<E> newNode, List<E> sorting, int splitPoint) { assert (isLeaf() == newNode.isLeaf()); deleteAllEntries(); - StringBuffer msg = LoggingConfiguration.DEBUG ? new StringBuffer("\n") : null; + StringBuilder msg = LoggingConfiguration.DEBUG ? new StringBuilder("\n") : null; for(int i = 0; i < splitPoint; i++) { addEntry(sorting.get(i)); @@ -373,7 +373,7 @@ public abstract class AbstractNode<E extends Entry> extends AbstractExternalizab public final void splitTo(AbstractNode<E> newNode, List<E> assignmentsToFirst, List<E> assignmentsToSecond) { assert (isLeaf() == newNode.isLeaf()); deleteAllEntries(); - StringBuffer msg = LoggingConfiguration.DEBUG ? new StringBuffer() : null; + StringBuilder msg = LoggingConfiguration.DEBUG ? new StringBuilder() : null; // assignments to this node for(E entry : assignmentsToFirst) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/IndexTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/IndexTree.java index e4cdc71f..13e91151 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/IndexTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/IndexTree.java @@ -44,7 +44,7 @@ public abstract class IndexTree<N extends Node<E>, E extends Entry> { /** * The file storing the entries of this index. */ - final private PageFile<N> file; + private final PageFile<N> file; /** * True if this index is already initialized. @@ -105,7 +105,7 @@ public abstract class IndexTree<N extends Node<E>, E extends Entry> { * * @return the static logger */ - abstract protected Logging getLogger(); + protected abstract Logging getLogger(); /** * Returns the entry representing the root if this index. @@ -213,6 +213,9 @@ public abstract class IndexTree<N extends Node<E>, E extends Entry> { /** * Initializes this index from an existing persistent file. + * + * @param header File header + * @param file Page file */ public void initializeFromFile(TreeIndexHeader header, PageFile<N> file) { this.dirCapacity = header.getDirCapacity(); @@ -221,7 +224,7 @@ public abstract class IndexTree<N extends Node<E>, E extends Entry> { this.leafMinimum = header.getLeafMinimum(); if(getLogger().isDebugging()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append(getClass()); msg.append("\n file = ").append(file.getClass()); getLogger().debugFine(msg.toString()); @@ -242,7 +245,7 @@ public abstract class IndexTree<N extends Node<E>, E extends Entry> { createEmptyRoot(exampleLeaf); if(getLogger().isDebugging()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append(getClass()).append("\n"); msg.append(" file = ").append(file.getClass()).append("\n"); msg.append(" maximum number of dir entries = ").append((dirCapacity - 1)).append("\n"); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/IndexTreePath.java b/src/de/lmu/ifi/dbs/elki/index/tree/IndexTreePath.java index 560bd250..2634ae07 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/IndexTreePath.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/IndexTreePath.java @@ -284,7 +284,7 @@ public class IndexTreePath<E extends Entry> { */ @Override public String toString() { - StringBuffer buffer = new StringBuffer("["); + StringBuilder buffer = new StringBuilder("["); for(int counter = 0, maxCounter = getPathCount(); counter < maxCounter; counter++) { if(counter > 0) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/TreeIndexFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/TreeIndexFactory.java index a170ca5b..c40effe5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/TreeIndexFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/TreeIndexFactory.java @@ -60,7 +60,7 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto * Key: {@code -treeindex.file} * </p> */ - public static final OptionID FILE_ID = OptionID.getOrCreateOptionID("treeindex.file", "The name of the file storing the index. " + "If this parameter is not set the index is hold in the main memory."); + public static final OptionID FILE_ID = new OptionID("treeindex.file", "The name of the file storing the index. " + "If this parameter is not set the index is hold in the main memory."); /** * Parameter to specify the size of a page in bytes, must be an integer @@ -72,7 +72,7 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto * Key: {@code -treeindex.pagesize} * </p> */ - public static final OptionID PAGE_SIZE_ID = OptionID.getOrCreateOptionID("treeindex.pagesize", "The size of a page in bytes."); + public static final OptionID PAGE_SIZE_ID = new OptionID("treeindex.pagesize", "The size of a page in bytes."); /** * Parameter to specify the size of the cache in bytes, must be an integer @@ -84,7 +84,7 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto * Key: {@code -treeindex.cachesize} * </p> */ - public static final OptionID CACHE_SIZE_ID = OptionID.getOrCreateOptionID("treeindex.cachesize", "The size of the cache in bytes."); + public static final OptionID CACHE_SIZE_ID = new OptionID("treeindex.cachesize", "The size of the cache in bytes."); /** * Holds the name of the file storing the index specified by {@link #FILE_ID}, @@ -126,13 +126,12 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto // FIXME: make this single-shot when filename is set! protected <N extends ExternalizablePage> PageFile<N> makePageFile(Class<N> cls) { final PageFile<N> inner; - if(fileName == null) { + if (fileName == null) { inner = new MemoryPageFile<N>(pageSize); - } - else { + } else { inner = new PersistentPageFile<N>(pageSize, fileName, cls); } - if(cacheSize >= Integer.MAX_VALUE) { + if (cacheSize >= Integer.MAX_VALUE) { return inner; } return new LRUCache<N>(cacheSize, inner); @@ -148,7 +147,7 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto * * @apiviz.exclude */ - public static abstract class Parameterizer<O> extends AbstractParameterizer { + public abstract static class Parameterizer<O> extends AbstractParameterizer { protected String fileName = null; protected int pageSize; @@ -158,26 +157,28 @@ public abstract class TreeIndexFactory<O, I extends Index> implements IndexFacto @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - FileParameter FILE_PARAM = new FileParameter(FILE_ID, FileParameter.FileType.OUTPUT_FILE, true); - if(config.grab(FILE_PARAM)) { - fileName = FILE_PARAM.getValue().getPath(); - } - else { + FileParameter fileNameP = new FileParameter(FILE_ID, FileParameter.FileType.OUTPUT_FILE, true); + if (config.grab(fileNameP)) { + fileName = fileNameP.getValue().getPath(); + } else { fileName = null; } - final IntParameter PAGE_SIZE_PARAM = new IntParameter(PAGE_SIZE_ID, new GreaterConstraint(0), 4000); - if(config.grab(PAGE_SIZE_PARAM)) { - pageSize = PAGE_SIZE_PARAM.getValue(); + final IntParameter pageSizeP = new IntParameter(PAGE_SIZE_ID, 4000); + pageSizeP.addConstraint(new GreaterConstraint(0)); + if (config.grab(pageSizeP)) { + pageSize = pageSizeP.getValue(); } - LongParameter CACHE_SIZE_PARAM = new LongParameter(CACHE_SIZE_ID, new GreaterEqualConstraint(0), Integer.MAX_VALUE); - if(config.grab(CACHE_SIZE_PARAM)) { - cacheSize = CACHE_SIZE_PARAM.getValue(); + // FIXME: long, but limited to int values?!? + LongParameter cacheSizeP = new LongParameter(CACHE_SIZE_ID, Integer.MAX_VALUE); + cacheSizeP.addConstraint(new GreaterEqualConstraint(0)); + if (config.grab(cacheSizeP)) { + cacheSize = cacheSizeP.getValue(); } } @Override protected abstract TreeIndexFactory<O, ?> makeInstance(); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java index a35a4057..a7a063bd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants; import java.util.ArrayList; import java.util.Collections; import java.util.List; -import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; @@ -43,12 +42,8 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.MetricalIndexTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.split.Assignments; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.split.MLBDistSplit; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.split.MTreeSplit; -import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.persistent.PageFileUtil; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; /** * Abstract super class for all M-Tree variants. @@ -65,17 +60,17 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; */ public abstract class AbstractMTree<O, D extends Distance<D>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry<D>> extends MetricalIndexTree<O, D, N, E> { /** - * Debugging flag: do extra integrity checks + * Debugging flag: do extra integrity checks. */ - protected final static boolean extraIntegrityChecks = true; + protected static final boolean EXTRA_INTEGRITY_CHECKS = false; /** - * Holds the instance of the trees distance function + * Holds the instance of the trees distance function. */ protected DistanceFunction<O, D> distanceFunction; /** - * The distance query + * The distance query. */ protected DistanceQuery<O, D> distanceQuery; @@ -103,11 +98,11 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract } /** - * Get the distance factory + * Get the distance factory. * * @return the distance factory used */ - protected final D getDistanceFactory() { + public final D getDistanceFactory() { return distanceFunction.getDistanceFactory(); } @@ -120,7 +115,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract */ @Override public String toString() { - StringBuffer result = new StringBuffer(); + StringBuilder result = new StringBuilder(); int dirNodes = 0; int leafNodes = 0; int objects = 0; @@ -128,8 +123,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract N node = getRoot(); - while(!node.isLeaf()) { - if(node.getNumEntries() > 0) { + while (!node.isLeaf()) { + if (node.getNumEntries() > 0) { E entry = node.getEntry(0); node = getNode(entry); levels++; @@ -137,22 +132,20 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract } BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<N, E>(this, getRootPath()); - while(enumeration.hasMoreElements()) { + while (enumeration.hasMoreElements()) { IndexTreePath<E> path = enumeration.nextElement(); E entry = path.getLastPathComponent().getEntry(); - if(entry.isLeafEntry()) { + if (entry.isLeafEntry()) { objects++; result.append("\n ").append(entry.toString()); - } - else { + } else { node = getNode(entry); result.append("\n\n").append(node).append(", numEntries = ").append(node.getNumEntries()); result.append("\n").append(entry.toString()); - if(node.isLeaf()) { + if (node.isLeaf()) { leafNodes++; - } - else { + } else { dirNodes++; } } @@ -178,17 +171,17 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract */ // todo: implement a bulk load for M-Tree and remove this method public void insert(E entry, boolean withPreInsert) { - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("insert " + entry.getRoutingObjectID() + "\n"); } - if(!initialized) { + if (!initialized) { initialize(entry); } // choose subtree for insertion IndexTreePath<E> subtree = choosePath(entry, getRootPath()); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("insertion-subtree " + subtree + "\n"); } @@ -198,7 +191,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract entry.setParentDistance(parentDistance); // create leaf entry and do pre insert - if(withPreInsert) { + if (withPreInsert) { preInsert(entry); } @@ -211,8 +204,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract adjustTree(subtree); // test - if(extraIntegrityChecks) { - if(withPreInsert) { + if (EXTRA_INTEGRITY_CHECKS) { + if (withPreInsert) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -221,13 +214,13 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract /** * Bulk insert. * - * @param entries + * @param entries Entries to insert */ public void insertAll(List<E> entries) { - if(!initialized && entries.size() > 0) { + if (!initialized && entries.size() > 0) { initialize(entries.get(0)); } - for(E entry : entries) { + for (E entry : entries) { insert(entry, false); } } @@ -239,84 +232,6 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract } /** - * Performs a k-nearest neighbor query for the given FeatureVector with the - * given parameter k and the according distance function. The query result is - * in ascending order to the distance to the query object. - * - * @param q the id of the query object - * @param knnList the query result list - */ - protected final void doKNNQuery(DBID q, KNNHeap<D> knnList) { - final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); - - // push root - pq.add(new GenericMTreeDistanceSearchCandidate<D>(getDistanceFactory().nullDistance(), getRootID(), null)); - D d_k = knnList.getKNNDistance(); - - if (d_k == null) { - // Empty tree? - return; - } - - // search in tree - while(!pq.isEmpty()) { - GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll(); - - if(pqNode.mindist.compareTo(d_k) > 0) { - return; - } - - N node = getNode(pqNode.nodeID); - DBID o_p = pqNode.routingObjectID; - - // directory node - if(!node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - E entry = node.getEntry(i); - DBID o_r = entry.getRoutingObjectID(); - D r_or = entry.getCoveringRadius(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : getDistanceFactory().nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_r, o_p) : getDistanceFactory().nullDistance(); - - D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); - - D sum = d_k.plus(r_or); - - if(diff.compareTo(sum) <= 0) { - D d3 = distance(o_r, q); - D d_min = DistanceUtil.max(d3.minus(r_or), getDistanceFactory().nullDistance()); - if(d_min.compareTo(d_k) <= 0) { - pq.add(new GenericMTreeDistanceSearchCandidate<D>(d_min, getPageID(entry), o_r)); - } - } - } - - } - - // data node - else { - for(int i = 0; i < node.getNumEntries(); i++) { - E entry = node.getEntry(i); - DBID o_j = entry.getRoutingObjectID(); - - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : getDistanceFactory().nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_j, o_p) : getDistanceFactory().nullDistance(); - - D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); - - if(diff.compareTo(d_k) <= 0) { - D d3 = distanceQuery.distance(o_j, q); - if(d3.compareTo(d_k) <= 0) { - knnList.add(d3, o_j); - d_k = knnList.getKNNDistance(); - } - } - } - } - } - } - - /** * Chooses the best path of the specified subtree for insertion of the given * object. * @@ -328,90 +243,52 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract N node = getNode(subtree.getLastPathComponent().getEntry()); // leaf - if(node.isLeaf()) { + if (node.isLeaf()) { return subtree; } - D nullDistance = getDistanceFactory().nullDistance(); - List<DistanceEntry<D, E>> candidatesWithoutExtension = new ArrayList<DistanceEntry<D, E>>(); - List<DistanceEntry<D, E>> candidatesWithExtension = new ArrayList<DistanceEntry<D, E>>(); + DistanceEntry<D, E> bestCandidate; + D enlarge; // Track best enlargement - null for no enlargement needed. + // Initialize from first: + { + E entry = node.getEntry(0); + D distance = distance(object.getRoutingObjectID(), entry.getRoutingObjectID()); + bestCandidate = new DistanceEntry<D, E>(entry, distance, 0); + if (distance.compareTo(entry.getCoveringRadius()) <= 0) { + enlarge = null; + } else { + enlarge = distance.minus(entry.getCoveringRadius()); + } + } - for(int i = 0; i < node.getNumEntries(); i++) { + // Iterate over remaining + for (int i = 1; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); D distance = distance(object.getRoutingObjectID(), entry.getRoutingObjectID()); - D enlrg = distance.minus(entry.getCoveringRadius()); - if(enlrg.compareTo(nullDistance) <= 0) { - candidatesWithoutExtension.add(new DistanceEntry<D, E>(entry, distance, i)); - } - else { - candidatesWithExtension.add(new DistanceEntry<D, E>(entry, enlrg, i)); + if (distance.compareTo(entry.getCoveringRadius()) <= 0) { + if (enlarge != null || distance.compareTo(bestCandidate.getDistance()) < 0) { + bestCandidate = new DistanceEntry<D, E>(entry, distance, i); + enlarge = null; + } + } else if (enlarge != null) { + D enlrg = distance.minus(entry.getCoveringRadius()); + if (enlrg.compareTo(enlarge) < 0) { + bestCandidate = new DistanceEntry<D, E>(entry, distance, i); + enlarge = enlrg; + } } } - DistanceEntry<D, E> bestCandidate; - if(!candidatesWithoutExtension.isEmpty()) { - bestCandidate = Collections.min(candidatesWithoutExtension); - } - else { - Collections.sort(candidatesWithExtension); - bestCandidate = Collections.min(candidatesWithExtension); - E entry = bestCandidate.getEntry(); - D cr = entry.getCoveringRadius(); - entry.setCoveringRadius(cr.plus(bestCandidate.getDistance())); + // Apply enlargement + if (enlarge != null) { + bestCandidate.getEntry().setCoveringRadius(enlarge); } return choosePath(object, subtree.pathByAddingChild(new TreeIndexPathComponent<E>(bestCandidate.getEntry(), bestCandidate.getIndex()))); } /** - * Performs a batch k-nearest neigbor query for a list of query objects. - * - * @param node the node reprsenting the subtree on which the query should be - * performed - * @param ids the ids of th query objects - * @param knnLists the knn lists of the query objcets - * - * @deprecated Change to use by-object NN lookups instead. - */ - @Deprecated - protected final void batchNN(N node, DBIDs ids, Map<DBID, KNNHeap<D>> knnLists) { - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - E p = node.getEntry(i); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID q = iter.getDBID(); - KNNHeap<D> knns_q = knnLists.get(q); - D knn_q_maxDist = knns_q.getKNNDistance(); - - D dist_pq = distanceQuery.distance(p.getRoutingObjectID(), q); - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { - knns_q.add(dist_pq, p.getRoutingObjectID()); - } - } - } - } - else { - List<DistanceEntry<D, E>> entries = getSortedEntries(node, ids); - for(DistanceEntry<D, E> distEntry : entries) { - D minDist = distEntry.getDistance(); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID q = iter.getDBID(); - KNNHeap<D> knns_q = knnLists.get(q); - D knn_q_maxDist = knns_q.getKNNDistance(); - - if(minDist.compareTo(knn_q_maxDist) <= 0) { - E entry = distEntry.getEntry(); - N child = getNode(entry); - batchNN(child, ids, knnLists); - break; - } - } - } - } - } - - /** * Sorts the entries of the specified node according to their minimum distance * to the specified object. * @@ -422,10 +299,11 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract protected final List<DistanceEntry<D, E>> getSortedEntries(N node, DBID q) { List<DistanceEntry<D, E>> result = new ArrayList<DistanceEntry<D, E>>(); - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); D distance = distance(entry.getRoutingObjectID(), q); - D minDist = entry.getCoveringRadius().compareTo(distance) > 0 ? getDistanceFactory().nullDistance() : distance.minus(entry.getCoveringRadius()); + D radius = entry.getCoveringRadius(); + D minDist = radius.compareTo(distance) > 0 ? getDistanceFactory().nullDistance() : distance.minus(radius); result.add(new DistanceEntry<D, E>(entry, minDist, i)); } @@ -445,14 +323,15 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract protected final List<DistanceEntry<D, E>> getSortedEntries(N node, DBIDs ids) { List<DistanceEntry<D, E>> result = new ArrayList<DistanceEntry<D, E>>(); - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); + D radius = entry.getCoveringRadius(); D minMinDist = getDistanceFactory().infiniteDistance(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - D distance = distanceQuery.distance(entry.getRoutingObjectID(), iter.getDBID()); - D minDist = entry.getCoveringRadius().compareTo(distance) > 0 ? getDistanceFactory().nullDistance() : distance.minus(entry.getCoveringRadius()); - minMinDist = DistanceUtil.max(minMinDist, minDist); + D distance = distanceQuery.distance(entry.getRoutingObjectID(), iter); + D minDist = radius.compareTo(distance) > 0 ? getDistanceFactory().nullDistance() : distance.minus(radius); + minMinDist = DistanceUtil.min(minMinDist, minDist); } result.add(new DistanceEntry<D, E>(entry, minMinDist, i)); } @@ -469,27 +348,13 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract * @return the distance between the two specified ids */ protected final D distance(DBID id1, DBID id2) { - if(id1 == null || id2 == null) { + if (id1 == null || id2 == null) { return getDistanceFactory().undefinedDistance(); } return distanceQuery.distance(id1, id2); } /** - * Returns the distance between the given object and the id. - * - * @param id1 the first id - * @param o2 the second object - * @return the distance between the two specified objects - */ - protected final D distance(DBID id1, O o2) { - if(id1 == null) { - return getDistanceFactory().undefinedDistance(); - } - return distanceQuery.distance(id1, o2); - } - - /** * Creates a new directory entry representing the specified node. * * @param node the node to be represented by the new entry @@ -498,7 +363,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract * the routing object of the parent node * @return the newly created directory entry */ - abstract protected E createNewDirectoryEntry(N node, DBID routingObjectID, D parentDistance); + protected abstract E createNewDirectoryEntry(N node, DBID routingObjectID, D parentDistance); /** * Splits the specified node and returns the split result. @@ -512,10 +377,9 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract MTreeSplit<O, D, N, E> split = new MLBDistSplit<O, D, N, E>(node, distanceQuery); Assignments<D, E> assignments = split.getAssignments(); final N newNode; - if(node.isLeaf()) { + if (node.isLeaf()) { newNode = createNewLeafNode(); - } - else { + } else { newNode = createNewDirectoryNode(); } node.splitTo(newNode, assignments.getFirstAssignments(), assignments.getSecondAssignments()); @@ -524,7 +388,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract writeNode(node); writeNode(newNode); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { String msg = "Split Node " + node.getPageID() + " (" + this.getClass() + ")\n" + " newNode " + newNode.getPageID() + "\n" + " firstPromoted " + assignments.getFirstRoutingObject() + "\n" + " firstAssignments(" + node.getPageID() + ") " + assignments.getFirstAssignments() + "\n" + " firstCR " + assignments.getFirstCoveringRadius() + "\n" + " secondPromoted " + assignments.getSecondRoutingObject() + "\n" + " secondAssignments(" + newNode.getPageID() + ") " + assignments.getSecondAssignments() + "\n" + " secondCR " + assignments.getSecondCoveringRadius() + "\n"; getLogger().debugFine(msg); } @@ -533,38 +397,12 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract } /** - * Sorts the entries of the specified node according to their minimum distance - * to the specified objects. - * - * @param node the node - * @param ids the ids of the objects - * @return a list of the sorted entries - */ - // FIXME: Duplicate from above? - /* - * private List<DistanceEntry<D, E>> getSortedEntries(N node, DBIDs ids) { - * List<DistanceEntry<D, E>> result = new ArrayList<DistanceEntry<D, E>>(); - * - * for(int i = 0; i < node.getNumEntries(); i++) { E entry = node.getEntry(i); - * - * D minMinDist = distanceFunction.infiniteDistance(); for(DBID q : ids) { D - * distance = distance(entry.getRoutingObjectID(), q); D minDist = - * entry.getCoveringRadius().compareTo(distance) > 0 ? - * distanceFunction.nullDistance() : - * distance.minus(entry.getCoveringRadius()); if(minDist.compareTo(minMinDist) - * < 0) { minMinDist = minDist; } } result.add(new DistanceEntry<D, E>(entry, - * minMinDist, i)); } - * - * Collections.sort(result); return result; } - */ - - /** * Adjusts the tree after insertion of some nodes. * * @param subtree the subtree to be adjusted */ private void adjustTree(IndexTreePath<E> subtree) { - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("Adjust tree " + subtree + "\n"); } @@ -573,14 +411,14 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract N node = getNode(subtree.getLastPathComponent().getEntry()); // overflow in node; split the node - if(hasOverflow(node)) { + if (hasOverflow(node)) { SplitResult splitResult = split(node); N splitNode = splitResult.newNode; Assignments<D, E> assignments = splitResult.split.getAssignments(); // if root was split: create a new root that points the two split // nodes - if(isRoot(node)) { + if (isRoot(node)) { // FIXME: stimmen die parentDistance der Kinder in node & splitNode? IndexTreePath<E> newRootPath = createNewRoot(node, splitNode, assignments.getFirstRoutingObject(), assignments.getSecondRoutingObject()); adjustTree(newRootPath); @@ -590,7 +428,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract // get the parent and add the new split node E parentEntry = subtree.getParentPath().getLastPathComponent().getEntry(); N parent = getNode(parentEntry); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { getLogger().debugFine("parent " + parent); } D parentDistance2 = distance(parentEntry.getRoutingObjectID(), assignments.getSecondRoutingObject()); @@ -612,7 +450,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract // no overflow, only adjust parameters of the entry representing the // node else { - if(!isRoot(node)) { + if (!isRoot(node)) { E parentEntry = subtree.getParentPath().getLastPathComponent().getEntry(); N parent = getNode(parentEntry); int index = subtree.getLastPathComponent().getIndex(); @@ -639,7 +477,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract * otherwise */ private boolean hasOverflow(N node) { - if(node.isLeaf()) { + if (node.isLeaf()) { return node.getNumEntries() == leafCapacity; } @@ -665,9 +503,9 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract // switch the ids oldRoot.setPageID(root.getPageID()); - if(!oldRoot.isLeaf()) { + if (!oldRoot.isLeaf()) { // FIXME: what is happening here? - for(int i = 0; i < oldRoot.getNumEntries(); i++) { + for (int i = 0; i < oldRoot.getNumEntries(); i++) { N node = getNode(oldRoot.getEntry(i)); writeNode(node); } @@ -691,7 +529,7 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract writeNode(root); writeNode(oldRoot); writeNode(newNode); - if(getLogger().isDebugging()) { + if (getLogger().isDebugging()) { String msg = "Create new Root: ID=" + root.getPageID(); msg += "\nchild1 " + oldRoot; msg += "\nchild2 " + newNode; @@ -707,10 +545,22 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract * @apiviz.composedOf MTreeSplit */ private class SplitResult { + /** + * Split used + */ protected MTreeSplit<O, D, N, E> split; + /** + * New sibling + */ protected N newNode; + /** + * Constructor. + * + * @param split Split that was used + * @param newNode New sibling + */ public SplitResult(MTreeSplit<O, D, N, E> split, N newNode) { this.split = split; this.newNode = newNode; @@ -721,16 +571,13 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract public List<E> getLeaves() { List<E> result = new ArrayList<E>(); BreadthFirstEnumeration<N, E> enumeration = new BreadthFirstEnumeration<N, E>(this, getRootPath()); - while(enumeration.hasMoreElements()) { + while (enumeration.hasMoreElements()) { IndexTreePath<E> path = enumeration.nextElement(); E entry = path.getLastPathComponent().getEntry(); - if(entry.isLeafEntry()) { - // ignore, we are within a leaf! - } - else { + if (!entry.isLeafEntry()) { // TODO: any way to skip unnecessary reads? N node = getNode(entry); - if(node.isLeaf()) { + if (node.isLeaf()) { result.add(entry); } } @@ -747,8 +594,8 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract int levels = 0; N node = getRoot(); - while(!node.isLeaf()) { - if(node.getNumEntries() > 0) { + while (!node.isLeaf()) { + if (node.getNumEntries() > 0) { E entry = node.getEntry(0); node = getNode(entry); levels++; @@ -756,4 +603,4 @@ public abstract class AbstractMTree<O, D extends Distance<D>, N extends Abstract } return levels; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java index 9ae50bbe..3769a562 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTreeFactory.java @@ -60,7 +60,7 @@ public abstract class AbstractMTreeFactory<O, D extends Distance<D>, N extends A * {@link de.lmu.ifi.dbs.elki.distance.distancefunction.EuclideanDistanceFunction} * </p> */ - public static final OptionID DISTANCE_FUNCTION_ID = OptionID.getOrCreateOptionID("mtree.distancefunction", "Distance function to determine the distance between database objects."); + public static final OptionID DISTANCE_FUNCTION_ID = new OptionID("mtree.distancefunction", "Distance function to determine the distance between database objects."); /** * Holds the instance of the distance function specified by @@ -93,7 +93,7 @@ public abstract class AbstractMTreeFactory<O, D extends Distance<D>, N extends A * * @apiviz.exclude */ - public static abstract class Parameterizer<O, D extends Distance<D>> extends TreeIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O, D extends Distance<D>> extends TreeIndexFactory.Parameterizer<O> { protected DistanceFunction<O, D> distanceFunction = null; @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java index 0b07c446..3902973f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/MTreeDirectoryEntry.java @@ -152,7 +152,7 @@ public class MTreeDirectoryEntry<D extends Distance<D>> extends AbstractDirector @Override public void writeExternal(ObjectOutput out) throws IOException { super.writeExternal(out); - out.writeInt(routingObjectID.getIntegerID()); + out.writeInt(DBIDUtil.asInteger(routingObjectID)); out.writeObject(parentDistance); out.writeObject(coveringRadius); } @@ -209,6 +209,6 @@ public class MTreeDirectoryEntry<D extends Distance<D>> extends AbstractDirector if(parentDistance != null ? !parentDistance.equals(that.parentDistance) : that.parentDistance != null) { return false; } - return !(routingObjectID != null ? !routingObjectID.equals(that.routingObjectID) : that.routingObjectID != null); + return !(routingObjectID != null ? !DBIDUtil.equal(routingObjectID, that.routingObjectID) : that.routingObjectID != null); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java index 9391a2fa..f3c440b5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTree.java @@ -23,16 +23,24 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; +import java.util.HashMap; +import java.util.Map; +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.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; /** @@ -48,6 +56,11 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; */ public abstract class AbstractMkTree<O, D extends Distance<D>, N extends AbstractMTreeNode<O, D, N, E>, E extends MTreeEntry<D>> extends AbstractMTree<O, D, N, E> { /** + * Internal class for performing knn queries + */ + protected KNNQuery<O, D> knnq; + + /** * Constructor. * * @param pagefile Page file @@ -56,8 +69,9 @@ public abstract class AbstractMkTree<O, D extends Distance<D>, N extends Abstrac */ public AbstractMkTree(PageFile<N> pagefile, DistanceQuery<O, D> distanceQuery, DistanceFunction<O, D> distanceFunction) { super(pagefile, distanceQuery, distanceFunction); + this.knnq = MTreeQueryUtil.getKNNQuery(this, distanceQuery); } - + /** * Performs a reverse k-nearest neighbor query for the given object ID. The * query result is in ascending order to the distance to the query object. @@ -66,5 +80,25 @@ public abstract class AbstractMkTree<O, D extends Distance<D>, N extends Abstrac * @param k the number of nearest neighbors to be returned * @return a List of the query results */ - public abstract List<DistanceResultPair<D>> reverseKNNQuery(final DBIDRef id, int k); -}
\ No newline at end of file + public abstract DistanceDBIDResult<D> reverseKNNQuery(final DBIDRef id, int k); + + /** + * Performs a batch k-nearest neighbor query for a list of query objects. + * + * @param node the node representing the subtree on which the query should be + * performed + * @param ids the ids of the query objects + * @param kmax Maximum k value + * + * @deprecated Change to use by-object NN lookups instead. + */ + @Deprecated + protected final Map<DBID, KNNResult<D>> batchNN(N node, DBIDs ids, int kmax) { + Map<DBID, KNNResult<D>> res = new HashMap<DBID, KNNResult<D>>(ids.size()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + res.put(id, knnq.getKNNForDBID(id, kmax)); + } + return res; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java index 88013000..34507479 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnified.java @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.HashMap; import java.util.List; import java.util.Map; @@ -32,12 +31,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.persistent.PageFile; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * Abstract class for all M-Tree variants supporting processing of reverse @@ -82,35 +81,29 @@ public abstract class AbstractMkTreeUnified<O, D extends Distance<D>, N extends @Override public void insertAll(List<E> entries) { - if(entries.size() <= 0) { + if (entries.size() <= 0) { return; } - if(!initialized) { + if (!initialized) { initialize(entries.get(0)); } - Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(); ModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); // insert sequentially - for(E entry : entries) { - // create knnList for the object - final DBID id = entry.getRoutingObjectID(); - - ids.add(id); - knnLists.put(id, new KNNHeap<D>(k_max, getDistanceFactory().infiniteDistance())); - + for (E entry : entries) { + ids.add(entry.getRoutingObjectID()); // insert the object super.insert(entry, false); } // do batch nn - batchNN(getRoot(), ids, knnLists); + Map<DBID, KNNResult<D>> knnLists = batchNN(getRoot(), ids, k_max); // adjust the knn distances kNNdistanceAdjustment(getRootEntry(), knnLists); - if(extraIntegrityChecks) { + if (EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -121,7 +114,7 @@ public abstract class AbstractMkTreeUnified<O, D extends Distance<D>, N extends * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - protected abstract void kNNdistanceAdjustment(E entry, Map<DBID, KNNHeap<D>> knnLists); + protected abstract void kNNdistanceAdjustment(E entry, Map<DBID, KNNResult<D>> knnLists); /** * Get the value of k_max. @@ -131,4 +124,4 @@ public abstract class AbstractMkTreeUnified<O, D extends Distance<D>, N extends public int getKmax() { return k_max; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java index 51df5077..9570995d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/AbstractMkTreeUnifiedFactory.java @@ -55,7 +55,7 @@ public abstract class AbstractMkTreeUnifiedFactory<O, D extends Distance<D>, N e * Key: {@code -mktree.kmax} * </p> */ - public static final OptionID K_MAX_ID = OptionID.getOrCreateOptionID("mktree.kmax", "Specifies the maximal number k of reverse k nearest neighbors to be supported."); + public static final OptionID K_MAX_ID = new OptionID("mktree.kmax", "Specifies the maximal number k of reverse k nearest neighbors to be supported."); /** * Holds the value of parameter {@link #K_MAX_ID}. @@ -83,13 +83,14 @@ public abstract class AbstractMkTreeUnifiedFactory<O, D extends Distance<D>, N e * * @apiviz.exclude */ - public static abstract class Parameterizer<O, D extends Distance<D>> extends AbstractMTreeFactory.Parameterizer<O, D> { + public abstract static class Parameterizer<O, D extends Distance<D>> extends AbstractMTreeFactory.Parameterizer<O, D> { protected int k_max; @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - IntParameter k_maxP = new IntParameter(K_MAX_ID, new GreaterConstraint(0)); + IntParameter k_maxP = new IntParameter(K_MAX_ID); + k_maxP.addConstraint(new GreaterConstraint(0)); if (config.grab(k_maxP)) { k_max = k_maxP.getValue(); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java index 0f15a4a9..51d59e73 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTree.java @@ -24,11 +24,8 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp; */ import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; import java.util.List; import java.util.Map; -import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; @@ -37,10 +34,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultIter; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; @@ -49,8 +48,6 @@ import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.statistics.PolynomialRegression; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNList; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; /** @@ -69,7 +66,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(MkAppTree.class); + private static final Logging LOG = Logging.getLogger(MkAppTree.class); /** * Parameter k. @@ -130,41 +127,30 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree return; } - if(logger.isDebugging()) { - logger.debugFine("insert " + entries + "\n"); + if(LOG.isDebugging()) { + LOG.debugFine("insert " + entries + "\n"); } if(!initialized) { initialize(entries.get(0)); } - Map<DBID, KNNHeap<D>> knnHeaps = new HashMap<DBID, KNNHeap<D>>(entries.size()); ModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); // insert for(MkAppEntry<D> entry : entries) { - DBID id = entry.getRoutingObjectID(); - // create knnList for the object - knnHeaps.put(id, new KNNHeap<D>(k_max + 1, getDistanceQuery().infiniteDistance())); - - ids.add(id); + ids.add(entry.getRoutingObjectID()); // insert the object super.insert(entry, false); } // do batch nn - batchNN(getRoot(), ids, knnHeaps); - - // finish KNN lists (sort them completely) - Map<DBID, KNNList<D>> knnLists = new HashMap<DBID, KNNList<D>>(); - for(Entry<DBID, KNNHeap<D>> ent : knnHeaps.entrySet()) { - knnLists.put(ent.getKey(), ent.getValue().toKNNList()); - } - + Map<DBID, KNNResult<D>> knnLists = batchNN(getRoot(), ids, k_max + 1); + // adjust the knn distances adjustApproximatedKNNDistances(getRootEntry(), knnLists); - if(extraIntegrityChecks) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -178,9 +164,55 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { - List<DistanceResultPair<D>> result = doReverseKNNQuery(k, id); - Collections.sort(result); + public DistanceDBIDResult<D> reverseKNNQuery(DBIDRef id, int k) { + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); + final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); + + // push root + pq.add(new GenericMTreeDistanceSearchCandidate<D>(getDistanceQuery().nullDistance(), getRootID(), null, null)); + + // search in tree + while(!pq.isEmpty()) { + GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll(); + // FIXME: cache the distance to the routing object in the queue node! + + MkAppTreeNode<O, D> node = getNode(pqNode.nodeID); + + // directory node + if(!node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + MkAppEntry<D> entry = node.getEntry(i); + D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), id); + D minDist = entry.getCoveringRadius().compareTo(distance) > 0 ? getDistanceQuery().nullDistance() : distance.minus(entry.getCoveringRadius()); + + double approxValue = log ? Math.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); + if(approxValue < 0) { + approxValue = 0; + } + D approximatedKnnDist = getDistanceQuery().getDistanceFactory().fromDouble(approxValue); + + if(minDist.compareTo(approximatedKnnDist) <= 0) { + pq.add(new GenericMTreeDistanceSearchCandidate<D>(minDist, getPageID(entry), entry.getRoutingObjectID(), null)); + } + } + } + // data node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + MkAppLeafEntry<D> entry = (MkAppLeafEntry<D>) node.getEntry(i); + D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), id); + double approxValue = log ? StrictMath.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); + if(approxValue < 0) { + approxValue = 0; + } + D approximatedKnnDist = getDistanceQuery().getDistanceFactory().fromDouble(approxValue); + + if(distance.compareTo(approximatedKnnDist) <= 0) { + result.add(distance, entry.getRoutingObjectID()); + } + } + } + } return result; } @@ -215,7 +247,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } if(dirCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } // leafCapacity = (file.getPageSize() - overhead) / (objectID + @@ -228,90 +260,31 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } if(leafCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } initialized = true; - if(logger.isVerbose()) { - logger.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); - } - } - - /** - * Performs a reverse knn query. - * - * @param k the parameter k of the rknn query - * @param q the id of the query object - * @return the result of the reverse knn query - */ - private List<DistanceResultPair<D>> doReverseKNNQuery(int k, DBIDRef q) { - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); - final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); - - // push root - pq.add(new GenericMTreeDistanceSearchCandidate<D>(getDistanceQuery().nullDistance(), getRootID(), null)); - - // search in tree - while(!pq.isEmpty()) { - GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll(); - - MkAppTreeNode<O, D> node = getNode(pqNode.nodeID); - - // directory node - if(!node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - MkAppEntry<D> entry = node.getEntry(i); - D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), q); - D minDist = entry.getCoveringRadius().compareTo(distance) > 0 ? getDistanceQuery().nullDistance() : distance.minus(entry.getCoveringRadius()); - - double approxValue = log ? Math.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); - if(approxValue < 0) { - approxValue = 0; - } - D approximatedKnnDist = getDistanceQuery().getDistanceFactory().parseString(Double.toString(approxValue)); - - if(minDist.compareTo(approximatedKnnDist) <= 0) { - pq.add(new GenericMTreeDistanceSearchCandidate<D>(minDist, getPageID(entry), entry.getRoutingObjectID())); - } - } - } - // data node - else { - for(int i = 0; i < node.getNumEntries(); i++) { - MkAppLeafEntry<D> entry = (MkAppLeafEntry<D>) node.getEntry(i); - D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), q); - double approxValue = log ? StrictMath.exp(entry.approximatedValueAt(k)) : entry.approximatedValueAt(k); - if(approxValue < 0) { - approxValue = 0; - } - D approximatedKnnDist = getDistanceQuery().getDistanceFactory().parseString(Double.toString(approxValue)); - - if(distance.compareTo(approximatedKnnDist) <= 0) { - result.add(new GenericDistanceResultPair<D>(distance, entry.getRoutingObjectID())); - } - } - } + if(LOG.isVerbose()) { + LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); } - return result; } - private List<D> getMeanKNNList(DBIDs ids, Map<DBID, KNNList<D>> knnLists) { + private List<D> getMeanKNNList(DBIDs ids, Map<DBID, KNNResult<D>> knnLists) { double[] means = new double[k_max]; - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - KNNList<D> knns = knnLists.get(id); - List<D> knnDists = knns.asDistanceList(); - for(int k = 0; k < k_max; k++) { - D knnDist = knnDists.get(k); - means[k] += knnDist.doubleValue(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + KNNResult<D> knns = knnLists.get(id); + int k = 0; + for(DistanceDBIDResultIter<D> it = knns.iter(); k < k_max && it.valid(); it.advance(), k++) { + means[k] += it.getDistance().doubleValue(); } } List<D> result = new ArrayList<D>(); for(int k = 0; k < k_max; k++) { means[k] /= ids.size(); - result.add(getDistanceQuery().getDistanceFactory().parseString(Double.toString(means[k]))); + result.add(getDistanceQuery().getDistanceFactory().fromDouble(means[k])); } return result; @@ -323,7 +296,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - private void adjustApproximatedKNNDistances(MkAppEntry<D> entry, Map<DBID, KNNList<D>> knnLists) { + private void adjustApproximatedKNNDistances(MkAppEntry<D> entry, Map<DBID, KNNResult<D>> knnLists) { MkAppTreeNode<O, D> node = getNode(entry); if(node.isLeaf()) { @@ -378,7 +351,7 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return the polynomial approximation of the specified knn-distances. */ private PolynomialApproximation approximateKnnDistances(List<D> knnDistances) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); // count the zero distances (necessary of log-log space is used) int k_0 = 0; @@ -411,9 +384,9 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree PolynomialRegression regression = new PolynomialRegression(y, x, p); PolynomialApproximation approximation = new PolynomialApproximation(regression.getEstimatedCoefficients().getArrayCopy()); - if(logger.isDebugging()) { + if(LOG.isDebugging()) { msg.append("approximation ").append(approximation); - logger.debugFine(msg.toString()); + LOG.debugFine(msg.toString()); } return approximation; @@ -464,6 +437,6 @@ public class MkAppTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java index 233129b4..c0f12895 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeFactory.java @@ -50,17 +50,17 @@ public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac /** * Parameter for nolog */ - public static final OptionID NOLOG_ID = OptionID.getOrCreateOptionID("mkapp.nolog", "Flag to indicate that the approximation is done in the ''normal'' space instead of the log-log space (which is default)."); + public static final OptionID NOLOG_ID = new OptionID("mkapp.nolog", "Flag to indicate that the approximation is done in the ''normal'' space instead of the log-log space (which is default)."); /** * Parameter for k */ - public static final OptionID K_ID = OptionID.getOrCreateOptionID("mkapp.k", "positive integer specifying the maximum number k of reverse k nearest neighbors to be supported."); + public static final OptionID K_ID = new OptionID("mkapp.k", "positive integer specifying the maximum number k of reverse k nearest neighbors to be supported."); /** * Parameter for p */ - public static final OptionID P_ID = OptionID.getOrCreateOptionID("mkapp.p", "positive integer specifying the order of the polynomial approximation."); + public static final OptionID P_ID = new OptionID("mkapp.p", "positive integer specifying the order of the polynomial approximation."); /** * Parameter k. @@ -131,19 +131,21 @@ public class MkAppTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - IntParameter K_PARAM = new IntParameter(K_ID, new GreaterConstraint(0)); - if(config.grab(K_PARAM)) { - k_max = K_PARAM.getValue(); + IntParameter kP = new IntParameter(K_ID); + kP.addConstraint(new GreaterConstraint(0)); + if(config.grab(kP)) { + k_max = kP.getValue(); } - IntParameter P_PARAM = new IntParameter(P_ID, new GreaterConstraint(0)); - if(config.grab(P_PARAM)) { - p = P_PARAM.getValue(); + IntParameter pP = new IntParameter(P_ID); + pP.addConstraint(new GreaterConstraint(0)); + if(config.grab(pP)) { + p = pP.getValue(); } - Flag NOLOG_FLAG = new Flag(NOLOG_ID); - if(config.grab(NOLOG_FLAG)) { - log = !NOLOG_FLAG.getValue(); + Flag nologF = new Flag(NOLOG_ID); + if(config.grab(nologF)) { + log = !nologF.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java index 90c31676..9776de63 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeIndex.java @@ -28,6 +28,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -43,8 +45,7 @@ import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexKNNQuery; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexRangeQuery; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MkTreeRKNNQuery; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; @@ -93,7 +94,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree } @Override - public void insert(DBID id) { + public void insert(DBIDRef id) { throw new UnsupportedOperationException("Insertion of single objects is not supported!"); } @@ -101,7 +102,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree public void insertAll(DBIDs ids) { List<MkAppEntry<D>> objs = new ArrayList<MkAppEntry<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } @@ -116,7 +117,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree * implemented yet. */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } @@ -154,7 +155,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexKNNQuery<O, S>(idx, dq); + return MTreeQueryUtil.getKNNQuery(idx, dq, hints); } @SuppressWarnings("unchecked") @@ -179,7 +180,7 @@ public class MkAppTreeIndex<O, D extends NumberDistance<D, ?>> extends MkAppTree } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexRangeQuery<O, S>(idx, dq); + return MTreeQueryUtil.getRangeQuery(idx, dq, hints); } @SuppressWarnings("unchecked") diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java index bc6a83a9..c730eb4f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkapp/MkAppTreeNode.java @@ -91,7 +91,7 @@ class MkAppTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode } if(LoggingConfiguration.DEBUG) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append("b " + FormatUtil.format(b, 4)); Logger.getLogger(this.getClass().getName()).fine(msg.toString()); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java index 7cb5a16b..6787aa9c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/ConvexHull.java @@ -112,7 +112,7 @@ public class ConvexHull { * should be computed */ private void determineLowerAndUpperHull(double[] x, double[] y) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); // first point is always in lowerHull and upperHull lowerHull[0] = 0; l = 1; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java index 26ae17db..562f7f4a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTree.java @@ -24,21 +24,20 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; */ import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; import java.util.List; import java.util.Map; -import java.util.Map.Entry; 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.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultIter; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate; @@ -47,9 +46,6 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.FormatUtil; import de.lmu.ifi.dbs.elki.utilities.QueryStatistic; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNList; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; /** * MkCopTree is a metrical index structure based on the concepts of the M-Tree @@ -68,7 +64,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(MkCoPTree.class); + private static final Logging LOG = Logging.getLogger(MkCoPTree.class); /** * Parameter k. @@ -125,41 +121,30 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree return; } - if(logger.isDebugging()) { - logger.debugFine("insert " + entries + "\n"); + if(LOG.isDebugging()) { + LOG.debugFine("insert " + entries + "\n"); } if(!initialized) { initialize(entries.get(0)); } - Map<DBID, KNNHeap<D>> knnHeaps = new HashMap<DBID, KNNHeap<D>>(entries.size()); ModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); // insert for(MkCoPEntry<D> entry : entries) { - DBID id = entry.getRoutingObjectID(); - // create knnList for the object - knnHeaps.put(id, new KNNHeap<D>(k_max + 1, getDistanceQuery().infiniteDistance())); - - ids.add(id); + ids.add(entry.getRoutingObjectID()); // insert the object super.insert(entry, false); } - // do batch nn - batchNN(getRoot(), ids, knnHeaps); - - // finish KNN lists (sort them completely) - Map<DBID, KNNList<D>> knnLists = new HashMap<DBID, KNNList<D>>(); - for(Entry<DBID, KNNHeap<D>> ent : knnHeaps.entrySet()) { - knnLists.put(ent.getKey(), ent.getValue().toKNNList()); - } + // perform nearest neighbor queries + Map<DBID, KNNResult<D>> knnLists = batchNN(getRoot(), ids, k_max); // adjust the knn distances adjustApproximatedKNNDistances(getRootEntry(), knnLists); - if(extraIntegrityChecks) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this, getRootEntry()); } } @@ -173,38 +158,35 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @return a List of the query results */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { + public DistanceDBIDResult<D> reverseKNNQuery(DBIDRef id, int k) { if(k > this.k_max) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MCop-Tree!"); } - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); ModifiableDBIDs candidates = DBIDUtil.newArray(); doReverseKNNQuery(k, id, result, candidates); // refinement of candidates - Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(); - for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { - knnLists.put(iter.getDBID(), new KNNHeap<D>(k, getDistanceQuery().infiniteDistance())); - } - batchNN(getRoot(), candidates, knnLists); + Map<DBID, KNNResult<D>> knnLists = batchNN(getRoot(), candidates, k); - Collections.sort(result); + result.sort(); // Collections.sort(candidates); rkNNStatistics.addCandidates(candidates.size()); rkNNStatistics.addTrueHits(result.size()); - for (DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { - DBID cid = iter.getDBID(); - for(DistanceResultPair<D> qr : knnLists.get(id)) { - if(qr.getDBID().equals(id)) { - result.add(new GenericDistanceResultPair<D>(qr.getDistance(), cid)); + for(DBIDIter iter = candidates.iter(); iter.valid(); iter.advance()) { + DBID cid = DBIDUtil.deref(iter); + KNNResult<D> cands = knnLists.get(cid); + for (DistanceDBIDResultIter<D> iter2 = cands.iter(); iter2.valid(); iter2.advance()) { + if(DBIDUtil.equal(id, iter2)) { + result.add(iter2.getDistance(), cid); break; } } } - Collections.sort(result); + result.sort(); rkNNStatistics.addResults(result.size()); return result; @@ -257,10 +239,11 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } if(dirCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } - // leafCapacity = (file.getPageSize() - overhead) / (objectID + parentDistance + + // leafCapacity = (file.getPageSize() - overhead) / (objectID + + // parentDistance + // consApprox + progrApprox) + 1 leafCapacity = (int) (getPageSize() - overhead) / (4 + distanceSize + 2 * 10) + 1; @@ -269,13 +252,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } if(leafCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } initialized = true; - if(logger.isVerbose()) { - logger.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); + if(LOG.isVerbose()) { + LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); } } @@ -288,15 +271,16 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param candidates holds possible candidates for the result (they need a * refinement) */ - private void doReverseKNNQuery(int k, DBIDRef q, List<DistanceResultPair<D>> result, ModifiableDBIDs candidates) { - final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); + private void doReverseKNNQuery(int k, DBIDRef q, GenericDistanceDBIDList<D> result, ModifiableDBIDs candidates) { + final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new Heap<GenericMTreeDistanceSearchCandidate<D>>(); // push root - pq.add(new GenericMTreeDistanceSearchCandidate<D>(getDistanceQuery().nullDistance(), getRootID(), null)); + pq.add(new GenericMTreeDistanceSearchCandidate<D>(getDistanceQuery().nullDistance(), getRootID(), null, null)); // search in tree while(!pq.isEmpty()) { GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll(); + // FIXME: cache the distance to the routing object in the queue node! MkCoPTreeNode<O, D> node = getNode(pqNode.nodeID); @@ -309,7 +293,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree D approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k, getDistanceQuery()); if(minDist.compareTo(approximatedKnnDist_cons) <= 0) { - pq.add(new GenericMTreeDistanceSearchCandidate<D>(minDist, getPageID(entry), entry.getRoutingObjectID())); + pq.add(new GenericMTreeDistanceSearchCandidate<D>(minDist, getPageID(entry), entry.getRoutingObjectID(), null)); } } } @@ -321,7 +305,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree D approximatedKnnDist_prog = entry.approximateProgressiveKnnDistance(k, getDistanceQuery()); if(distance.compareTo(approximatedKnnDist_prog) <= 0) { - result.add(new GenericDistanceResultPair<D>(distance, entry.getRoutingObjectID())); + result.add(distance, entry.getRoutingObjectID()); } else { D approximatedKnnDist_cons = entry.approximateConservativeKnnDistance(k, getDistanceQuery()); @@ -341,7 +325,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param entry the root entry of the current subtree * @param knnLists a map of knn lists for each leaf entry */ - private void adjustApproximatedKNNDistances(MkCoPEntry<D> entry, Map<DBID, KNNList<D>> knnLists) { + private void adjustApproximatedKNNDistances(MkCoPEntry<D> entry, Map<DBID, KNNResult<D>> knnLists) { MkCoPTreeNode<O, D> node = getNode(entry); if(node.isLeaf()) { @@ -393,10 +377,10 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree * @param knnDistances TODO: Spezialbehandlung fuer identische Punkte in DB * (insbes. Distanz 0) */ - private void approximateKnnDistances(MkCoPLeafEntry<D> entry, KNNList<D> knnDistances) { - StringBuffer msg = new StringBuffer(); - if(logger.isDebugging()) { - msg.append("\nknnDistances " + knnDistances); + private void approximateKnnDistances(MkCoPLeafEntry<D> entry, KNNResult<D> knnDistances) { + StringBuilder msg = LOG.isDebugging() ? new StringBuilder() : null; + if(msg != null) { + msg.append("\nknnDistances ").append(knnDistances); } // count the zero distances @@ -434,16 +418,16 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree sum_log_k2 += (log_k[i] * log_k[i]); } - if(logger.isDebugging()) { - msg.append("\nk_0 " + k_0); - msg.append("\nk_max " + k_max); - msg.append("\nlog_k(" + log_k.length + ") " + FormatUtil.format(log_k)); - msg.append("\nsum_log_k " + sum_log_k); - msg.append("\nsum_log_k^2 " + sum_log_k2); - msg.append("\nkDists " + knnDistances); - msg.append("\nlog_kDist(" + log_kDist.length + ") " + FormatUtil.format(log_kDist)); - msg.append("\nsum_log_kDist " + sum_log_kDist); - msg.append("\nsum_log_k_kDist " + sum_log_k_kDist); + if(msg != null) { + msg.append("\nk_0 ").append(k_0); + msg.append("\nk_max ").append(k_max); + msg.append("\nlog_k(").append(log_k.length).append(") ").append(FormatUtil.format(log_k)); + msg.append("\nsum_log_k ").append(sum_log_k); + msg.append("\nsum_log_k^2 ").append(sum_log_k2); + msg.append("\nkDists ").append(knnDistances); + msg.append("\nlog_kDist(").append(log_kDist.length).append(") ").append(FormatUtil.format(log_kDist)); + msg.append("\nsum_log_kDist ").append(sum_log_kDist); + msg.append("\nsum_log_k_kDist ").append(sum_log_k_kDist); } // lower and upper hull @@ -457,28 +441,28 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double err1 = ssqerr(k_0, k_max, log_k, log_kDist, conservative.getM(), conservative.getT()); double err2 = ssqerr(k_0, k_max, log_k, log_kDist, c2.getM(), c2.getT()); - if(logger.isDebugging()) { - msg.append("err1 " + err1); - msg.append("err2 " + err2); + if(msg != null) { + msg.append("err1 ").append(err1); + msg.append("err2 ").append(err2); } if(err1 > err2 && err1 - err2 > 0.000000001) { // if (err1 > err2) { - StringBuffer warning = new StringBuffer(); + StringBuilder warning = new StringBuilder(); int u = convexHull.getNumberOfPointsInUpperHull(); int[] upperHull = convexHull.getUpperHull(); - warning.append("\nentry " + entry.getRoutingObjectID()); - warning.append("\nlower Hull " + convexHull.getNumberOfPointsInLowerHull() + " " + FormatUtil.format(convexHull.getLowerHull())); - warning.append("\nupper Hull " + convexHull.getNumberOfPointsInUpperHull() + " " + FormatUtil.format(convexHull.getUpperHull())); - warning.append("\nerr1 " + err1); - warning.append("\nerr2 " + err2); - warning.append("\nconservative1 " + conservative); - warning.append("\nconservative2 " + c2); + warning.append("\nentry ").append(entry.getRoutingObjectID()); + warning.append("\nlower Hull ").append(convexHull.getNumberOfPointsInLowerHull()).append(" ").append(FormatUtil.format(convexHull.getLowerHull())); + warning.append("\nupper Hull ").append(convexHull.getNumberOfPointsInUpperHull()).append(" ").append(FormatUtil.format(convexHull.getUpperHull())); + warning.append("\nerr1 ").append(err1); + warning.append("\nerr2 ").append(err2); + warning.append("\nconservative1 ").append(conservative); + warning.append("\nconservative2 ").append(c2); for(int i = 0; i < u; i++) { - warning.append("\nlog_k[" + upperHull[i] + "] = " + log_k[upperHull[i]]); - warning.append("\nlog_kDist[" + upperHull[i] + "] = " + log_kDist[upperHull[i]]); + warning.append("\nlog_k[").append(upperHull[i]).append("] = ").append(log_k[upperHull[i]]); + warning.append("\nlog_kDist[").append(upperHull[i]).append("] = ").append(log_kDist[upperHull[i]]); } // warning(warning.toString()); } @@ -489,10 +473,9 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree entry.setConservativeKnnDistanceApproximation(conservative); entry.setProgressiveKnnDistanceApproximation(progressive); - if(logger.isDebugging()) { - logger.debugFine(msg.toString()); + if(msg != null) { + LOG.debugFine(msg.toString()); } - } /** @@ -505,13 +488,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree */ private ApproximationLine approximateLowerHull(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); int[] lowerHull = convexHull.getLowerHull(); int l = convexHull.getNumberOfPointsInLowerHull(); int k_0 = k_max - lowerHull.length + 1; // linear search on all line segments on the lower convex hull - msg.append("lower hull l = " + l + "\n"); + msg.append("lower hull l = ").append(l).append("\n"); double low_error = Double.MAX_VALUE; double low_m = 0.0; double low_t = 0.0; @@ -520,7 +503,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double cur_m = (log_kDist[lowerHull[i]] - log_kDist[lowerHull[i - 1]]) / (log_k[lowerHull[i]] - log_k[lowerHull[i - 1]]); double cur_t = log_kDist[lowerHull[i]] - cur_m * log_k[lowerHull[i]]; double cur_error = ssqerr(k_0, k_max, log_k, log_kDist, cur_m, cur_t); - msg.append(" Segment = " + i + " m = " + cur_m + " t = " + cur_t + " lowerror = " + cur_error + "\n"); + msg.append(" Segment = ").append(i).append(" m = ").append(cur_m).append(" t = ").append(cur_t).append(" lowerror = ").append(cur_error).append("\n"); if(cur_error < low_error) { low_error = cur_error; low_m = cur_m; @@ -557,7 +540,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } private ApproximationLine approximateUpperHull(ConvexHull convexHull, double[] log_k, double[] log_kDist) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); int[] upperHull = convexHull.getUpperHull(); int u = convexHull.getNumberOfPointsInUpperHull(); @@ -572,13 +555,13 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double current_t = log_kDist[ii] - current_m * log_k[ii]; ApproximationLine current_approx = new ApproximationLine(k_0, current_m, current_t); - if(logger.isDebugging()) { - msg.append("\nlog_kDist[" + jj + "] " + log_kDist[jj]); - msg.append("\nlog_kDist[" + ii + "] " + log_kDist[ii]); - msg.append("\nlog_k[" + jj + "] " + log_k[jj]); - msg.append("\nlog_k[" + ii + "] " + log_k[ii]); - msg.append("\n" + (log_kDist[jj] - log_kDist[ii])); - msg.append("\ncurrent_approx_" + i + " " + current_approx); + if(LOG.isDebugging()) { + msg.append("\nlog_kDist[").append(jj).append("] ").append(log_kDist[jj]); + msg.append("\nlog_kDist[").append(ii).append("] ").append(log_kDist[ii]); + msg.append("\nlog_k[").append(jj).append("] ").append(log_k[jj]); + msg.append("\nlog_k[").append(ii).append("] ").append(log_k[ii]); + msg.append("\n").append((log_kDist[jj] - log_kDist[ii])); + msg.append("\ncurrent_approx_").append(i).append(" ").append(current_approx); } boolean ok = true; @@ -598,15 +581,15 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree } } - if(logger.isDebugging()) { - msg.append("\nupper Approx " + approx); - logger.debugFine(msg.toString()); + if(LOG.isDebugging()) { + msg.append("\nupper Approx ").append(approx); + LOG.debugFine(msg.toString()); } return approx; } private ApproximationLine approximateUpperHull_PAPER(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = LOG.isDebugging() ? new StringBuilder() : null; int[] upperHull = convexHull.getUpperHull(); int u = convexHull.getNumberOfPointsInUpperHull(); @@ -624,9 +607,9 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree double m_a = optimize(k_0, k_max, sum_log_k, sum_log_k2, x_a, y_a, sum_log_k_kDist, sum_log_kDist); double t_a = y_a - m_a * x_a; - if(logger.isDebugging()) { - msg.append("\na=" + a + " m_a=" + m_a + ", t_a=" + t_a); - msg.append("\n err " + ssqerr(k_0, k_max, log_k, log_kDist, m_a, m_a)); + if(msg != null) { + msg.append("\na=").append(a).append(" m_a=").append(m_a).append(", t_a=").append(t_a); + msg.append("\n err ").append(ssqerr(k_0, k_max, log_k, log_kDist, m_a, m_a)); } double x_p = a == 0 ? Double.NaN : log_k[upperHull[a - 1]]; @@ -639,13 +622,12 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree if(lessThanPre && lessThanSuc) { ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if(logger.isDebugging()) { - msg.append("\n1 anchor = " + a); - logger.debugFine(msg.toString()); + if(msg != null) { + msg.append("\n1 anchor = ").append(a); + LOG.debugFine(msg.toString()); } return appr; } - else if(!lessThanPre) { if(marked.contains(a - 1)) { m_a = (y_a - y_p) / (x_a - x_p); @@ -655,14 +637,14 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree t_a = y_a - m_a * x_a; ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if(logger.isDebugging()) { - msg.append("2 anchor = " + a); - msg.append(" appr1 " + appr); - msg.append(" x_a " + x_a + ", y_a " + y_a); - msg.append(" x_p " + x_p + ", y_p " + y_p); - msg.append(" a " + a); - msg.append(" upperHull " + FormatUtil.format(upperHull)); - logger.debugFine(msg.toString()); + if(msg != null) { + msg.append("2 anchor = ").append(a); + msg.append(" appr1 ").append(appr); + msg.append(" x_a ").append(x_a).append(", y_a ").append(y_a); + msg.append(" x_p ").append(x_p).append(", y_p ").append(y_p); + msg.append(" a ").append(a); + msg.append(" upperHull ").append(FormatUtil.format(upperHull)); + LOG.debugFine(msg.toString()); } return appr; } @@ -679,10 +661,10 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree t_a = y_a - m_a * x_a; ApproximationLine appr = new ApproximationLine(k_0, m_a, t_a); - if(logger.isDebugging()) { - msg.append("3 anchor = " + a + " -- " + (a + 1)); - msg.append(" appr2 " + appr); - logger.debugFine(msg.toString()); + if(msg != null) { + msg.append("3 anchor = ").append(a).append(" -- ").append((a + 1)); + msg.append(" appr2 ").append(appr); + LOG.debugFine(msg.toString()); } return appr; } @@ -698,7 +680,7 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree @SuppressWarnings("unused") private ApproximationLine approximateUpperHull_OLD(ConvexHull convexHull, double[] log_k, double sum_log_k, double sum_log_k2, double[] log_kDist, double sum_log_kDist, double sum_log_k_kDist) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); int[] upperHull = convexHull.getUpperHull(); int u = convexHull.getNumberOfPointsInUpperHull(); int k_0 = k_max - upperHull.length + 1; @@ -794,6 +776,6 @@ public class MkCoPTree<O, D extends NumberDistance<D, ?>> extends AbstractMkTree @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java index 460e15b7..d3e45f8c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeIndex.java @@ -28,6 +28,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -43,8 +45,7 @@ import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexKNNQuery; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexRangeQuery; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MkTreeRKNNQuery; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; @@ -92,7 +93,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree } @Override - public void insert(DBID id) { + public void insert(DBIDRef id) { throw new UnsupportedOperationException("Insertion of single objects is not supported!"); } @@ -100,7 +101,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree public void insertAll(DBIDs ids) { List<MkCoPEntry<D>> objs = new ArrayList<MkCoPEntry<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } @@ -115,7 +116,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree * implemented yet. */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } @@ -153,7 +154,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexKNNQuery<O, S>(idx, dq); + return MTreeQueryUtil.getKNNQuery(idx, dq, hints); } @SuppressWarnings("unchecked") @@ -178,7 +179,7 @@ public class MkCoPTreeIndex<O, D extends NumberDistance<D, ?>> extends MkCoPTree } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexRangeQuery<O, S>(idx, dq); + return MTreeQueryUtil.getRangeQuery(idx, dq, hints); } @SuppressWarnings("unchecked") diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java index 01fca2f2..f2e4a114 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCoPTreeNode.java @@ -23,13 +23,10 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkcop; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.logging.Logger; - import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; -import de.lmu.ifi.dbs.elki.logging.LoggingConfiguration; /** * Represents a node in an MkCop-Tree. @@ -99,15 +96,6 @@ class MkCoPTreeNode<O, D extends NumberDistance<D, ?>> extends AbstractMTreeNode } } - if(LoggingConfiguration.DEBUG) { - StringBuffer msg = new StringBuffer(); - msg.append("k_0 " + k_0); - msg.append("k_max " + k_max); - msg.append("y_1 " + y_1); - msg.append("y_kmax " + y_kmax); - Logger.getLogger(this.getClass().getName()).fine(msg.toString()); - } - // determine m and t double m = (y_kmax - y_1) / (Math.log(k_max) - Math.log(k_0)); double t = y_1 - m * Math.log(k_0); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java index 8d88ee79..4ac96df3 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkcop/MkCopTreeFactory.java @@ -49,7 +49,7 @@ public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac /** * Parameter for k */ - public static final OptionID K_ID = OptionID.getOrCreateOptionID("mkcop.k", "positive integer specifying the maximum number k of reverse k nearest neighbors to be supported."); + public static final OptionID K_ID = new OptionID("mkcop.k", "positive integer specifying the maximum number k of reverse k nearest neighbors to be supported."); /** * Parameter k. @@ -93,9 +93,10 @@ public class MkCopTreeFactory<O, D extends NumberDistance<D, ?>> extends Abstrac @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - IntParameter k_maxP = new IntParameter(K_ID, new GreaterConstraint(0)); + IntParameter k_maxP = new IntParameter(K_ID); + k_maxP.addConstraint(new GreaterConstraint(0)); if (config.grab(k_maxP)) { - k_max = k_maxP.getValue(); + k_max = k_maxP.intValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java index f9f77723..36f9bbf1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTree.java @@ -23,9 +23,6 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; import java.util.List; import java.util.Map; @@ -34,18 +31,22 @@ 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.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultIter; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; +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.distanceresultlist.ModifiableDistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DistanceEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.QueryStatistic; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * MkMaxTree is a metrical index structure based on the concepts of the M-Tree @@ -64,7 +65,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(MkMaxTree.class); + private static final Logging LOG = Logging.getLogger(MkMaxTree.class); /** * Provides some statistics about performed reverse knn-queries. @@ -90,38 +91,36 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * in a second step. */ @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { + public DistanceDBIDResult<D> reverseKNNQuery(DBIDRef id, int k) { if(k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be equal or less than " + "parameter k of the MkMax-Tree!"); } // get the candidates - List<DistanceResultPair<D>> candidates = new ArrayList<DistanceResultPair<D>>(); + GenericDistanceDBIDList<D> candidates = new GenericDistanceDBIDList<D>(); doReverseKNNQuery(id, getRoot(), null, candidates); if(k == this.getKmax()) { - Collections.sort(candidates); + candidates.sort(); rkNNStatistics.addTrueHits(candidates.size()); rkNNStatistics.addResults(candidates.size()); return candidates; } // refinement of candidates - Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(); - ModifiableDBIDs candidateIDs = DBIDUtil.newArray(); - for(DistanceResultPair<D> candidate : candidates) { - KNNHeap<D> knns = new KNNHeap<D>(k, getDistanceQuery().infiniteDistance()); - knnLists.put(candidate.getDBID(), knns); - candidateIDs.add(candidate.getDBID()); + ModifiableDBIDs candidateIDs = DBIDUtil.newArray(candidates.size()); + for (DBIDIter candidate = candidates.iter(); candidate.valid(); candidate.advance()) { + candidateIDs.add(candidate); } - batchNN(getRoot(), candidateIDs, knnLists); + Map<DBID, KNNResult<D>> knnLists = batchNN(getRoot(), candidateIDs, k); - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); for (DBIDIter iter = candidateIDs.iter(); iter.valid(); iter.advance()) { - DBID cid = iter.getDBID(); - for(DistanceResultPair<D> qr : knnLists.get(cid)) { - if(id.equals(qr.getDBID())) { - result.add(new GenericDistanceResultPair<D>(qr.getDistance(), cid)); + DBID cid = DBIDUtil.deref(iter); + KNNResult<D> cands = knnLists.get(cid); + for (DistanceDBIDResultIter<D> iter2 = cands.iter(); iter2.valid(); iter2.advance()) { + if(DBIDUtil.equal(id, iter2)) { + result.add(iter2.getDistance(), cid); break; } } @@ -129,7 +128,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O rkNNStatistics.addResults(result.size()); rkNNStatistics.addCandidates(candidates.size()); - Collections.sort(result); + result.sort(); return result; } @@ -155,7 +154,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O */ @Override protected void preInsert(MkMaxEntry<D> entry) { - KNNHeap<D> knns_o = new KNNHeap<D>(getKmax(), getDistanceQuery().infiniteDistance()); + KNNHeap<D> knns_o = KNNUtil.newHeap(distanceFunction, getKmax()); preInsert(entry, getRootEntry(), knns_o); } @@ -163,7 +162,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * Adjusts the knn distance in the subtree of the specified root entry. */ @Override - protected void kNNdistanceAdjustment(MkMaxEntry<D> entry, Map<DBID, KNNHeap<D>> knnLists) { + protected void kNNdistanceAdjustment(MkMaxEntry<D> entry, Map<DBID, KNNResult<D>> knnLists) { MkMaxTreeNode<O, D> node = getNode(entry); D knnDist_node = getDistanceQuery().nullDistance(); if(node.isLeaf()) { @@ -194,14 +193,14 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * @param node_entry the entry representing the node * @param result the list for the query result */ - private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O, D> node, MkMaxEntry<D> node_entry, List<DistanceResultPair<D>> result) { + private void doReverseKNNQuery(DBIDRef q, MkMaxTreeNode<O, D> node, MkMaxEntry<D> node_entry, ModifiableDistanceDBIDResult<D> result) { // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { MkMaxEntry<D> entry = node.getEntry(i); D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), q); if(distance.compareTo(entry.getKnnDistance()) <= 0) { - result.add(new GenericDistanceResultPair<D>(distance, entry.getRoutingObjectID())); + result.add(distance, entry.getRoutingObjectID()); } } } @@ -231,8 +230,8 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * @param knns_q the knns of q */ private void preInsert(MkMaxEntry<D> q, MkMaxEntry<D> nodeEntry, KNNHeap<D> knns_q) { - if(logger.isDebugging()) { - logger.debugFine("preInsert " + q + " - " + nodeEntry + "\n"); + if(LOG.isDebugging()) { + LOG.debugFine("preInsert " + q + " - " + nodeEntry + "\n"); } D knnDist_q = knns_q.getKNNDistance(); @@ -248,10 +247,9 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O // p is nearer to q than the farthest kNN-candidate of q // ==> p becomes a knn-candidate if(dist_pq.compareTo(knnDist_q) <= 0) { - DistanceResultPair<D> knn = new GenericDistanceResultPair<D>(dist_pq, p.getRoutingObjectID()); - knns_q.add(knn); + knns_q.add(dist_pq, p.getRoutingObjectID()); if(knns_q.size() >= getKmax()) { - knnDist_q = knns_q.getMaximumDistance(); + knnDist_q = knns_q.getKNNDistance(); q.setKnnDistance(knnDist_q); } @@ -259,15 +257,13 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O // p is nearer to q than to its farthest knn-candidate // q becomes knn of p if(dist_pq.compareTo(p.getKnnDistance()) <= 0) { - KNNHeap<D> knns_p = new KNNHeap<D>(getKmax(), getDistanceQuery().infiniteDistance()); - knns_p.add(new GenericDistanceResultPair<D>(dist_pq, q.getRoutingObjectID())); - doKNNQuery(p.getRoutingObjectID(), knns_p); + KNNResult<D> knns_p = knnq.getKNNForDBID(p.getRoutingObjectID(), getKmax() - 1); - if(knns_p.size() < getKmax()) { + if(knns_p.size() + 1 < getKmax()) { p.setKnnDistance(getDistanceQuery().undefinedDistance()); } else { - D knnDist_p = knns_p.getMaximumDistance(); + D knnDist_p = DistanceUtil.max(dist_pq, knns_p.getKNNDistance()); p.setKnnDistance(knnDist_p); } } @@ -288,8 +284,8 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O knnDist_node = DistanceUtil.max(knnDist_node, dirEntry.getKnnDistance()); } } - if(logger.isDebugging()) { - logger.debugFine(nodeEntry + "set knn dist " + knnDist_node); + if(LOG.isDebugging()) { + LOG.debugFine(nodeEntry + "set knn dist " + knnDist_node); } nodeEntry.setKnnDistance(knnDist_node); } @@ -313,7 +309,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } if(dirCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } // leafCapacity = (file.getPageSize() - overhead) / (objectID + @@ -326,7 +322,7 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } if(leafCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } } @@ -365,6 +361,6 @@ public class MkMaxTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java index d1fd2b0f..0bd31dca 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mkmax/MkMaxTreeIndex.java @@ -28,6 +28,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -36,22 +38,32 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexKNNQuery; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexRangeQuery; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MkTreeRKNNQuery; import de.lmu.ifi.dbs.elki.persistent.PageFile; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; +/** + * MkMax tree + * + * @author Elke Achtert + * + * @param <O> Object type + * @param <D> Distance type + */ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O> { + /** + * Relation indexed. + */ private Relation<O> relation; - + /** * Constructor. * @@ -71,22 +83,21 @@ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> im * @return a new MkMaxLeafEntry representing the specified data object */ protected MkMaxLeafEntry<D> createNewLeafEntry(DBID id, O object, D parentDistance) { - KNNHeap<D> knnList = new KNNHeap<D>(getKmax() - 1); - doKNNQuery(id, knnList); - D knnDistance = knnList.getMaximumDistance(); + KNNResult<D> knns = knnq.getKNNForObject(object, getKmax() - 1); + D knnDistance = knns.getKNNDistance(); return new MkMaxLeafEntry<D>(id, parentDistance, knnDistance); } @Override - public void insert(DBID id) { - insert(createNewLeafEntry(id, relation.get(id), getDistanceFactory().undefinedDistance()), false); + public void insert(DBIDRef id) { + insert(createNewLeafEntry(DBIDUtil.deref(id), relation.get(id), getDistanceFactory().undefinedDistance()), false); } @Override public void insertAll(DBIDs ids) { List<MkMaxEntry<D>> objs = new ArrayList<MkMaxEntry<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } @@ -101,7 +112,7 @@ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> im * implemented yet. */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } @@ -139,7 +150,7 @@ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> im } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexKNNQuery<O, S>(idx, dq); + return MTreeQueryUtil.getKNNQuery(idx, dq, hints); } @SuppressWarnings("unchecked") @@ -164,7 +175,7 @@ public class MkMaxTreeIndex<O, D extends Distance<D>> extends MkMaxTree<O, D> im } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexRangeQuery<O, S>(idx, dq); + return MTreeQueryUtil.getRangeQuery(idx, dq); } @SuppressWarnings("unchecked") diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java index 433a01fa..f5410839 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTree.java @@ -24,22 +24,22 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab; */ import java.util.ArrayList; -import java.util.Collections; import java.util.List; import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +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.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.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.persistent.PageFile; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * MkTabTree is a metrical index structure based on the concepts of the M-Tree @@ -58,7 +58,7 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(MkTabTree.class); + private static final Logging LOG = Logging.getLogger(MkTabTree.class); /** * Constructor. @@ -91,15 +91,15 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } @Override - public List<DistanceResultPair<D>> reverseKNNQuery(DBIDRef id, int k) { + public DistanceDBIDResult<D> reverseKNNQuery(DBIDRef id, int k) { if(k > this.getKmax()) { throw new IllegalArgumentException("Parameter k has to be less or equal than " + "parameter kmax of the MkTab-Tree!"); } - List<DistanceResultPair<D>> result = new ArrayList<DistanceResultPair<D>>(); + GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); doReverseKNNQuery(k, id, null, getRoot(), result); - Collections.sort(result); + result.sort(); return result; } @@ -122,7 +122,7 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } if(dirCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } // leafCapacity = (pageSize - overhead) / (objectID + parentDistance + + @@ -134,19 +134,18 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O } if(leafCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } - } - + @Override - protected void kNNdistanceAdjustment(MkTabEntry<D> entry, Map<DBID, KNNHeap<D>> knnLists) { + protected void kNNdistanceAdjustment(MkTabEntry<D> entry, Map<DBID, KNNResult<D>> knnLists) { MkTabTreeNode<O, D> node = getNode(entry); List<D> knnDistances_node = initKnnDistanceList(); if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry<D> leafEntry = node.getEntry(i); - leafEntry.setKnnDistances(knnLists.get(getPageID(leafEntry)).toKNNList().asDistanceList()); + leafEntry.setKnnDistances(KNNUtil.asDistanceList(knnLists.get(getPageID(leafEntry)))); knnDistances_node = max(knnDistances_node, leafEntry.getKnnDistances()); } } @@ -210,14 +209,14 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O * @param node the root of the subtree * @param result the list holding the query result */ - private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry<D> node_entry, MkTabTreeNode<O, D> node, List<DistanceResultPair<D>> result) { + private void doReverseKNNQuery(int k, DBIDRef q, MkTabEntry<D> node_entry, MkTabTreeNode<O, D> node, GenericDistanceDBIDList<D> result) { // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { MkTabEntry<D> entry = node.getEntry(i); D distance = getDistanceQuery().distance(entry.getRoutingObjectID(), q); if(distance.compareTo(entry.getKnnDistance(k)) <= 0) { - result.add(new GenericDistanceResultPair<D>(distance, entry.getRoutingObjectID())); + result.add(distance, entry.getRoutingObjectID()); } } } @@ -278,6 +277,6 @@ public class MkTabTree<O, D extends Distance<D>> extends AbstractMkTreeUnified<O @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java index f1d23bfd..b12ac059 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees/mktab/MkTabTreeIndex.java @@ -28,24 +28,25 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNUtil; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.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.KNNIndex; import de.lmu.ifi.dbs.elki.index.RKNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTreeUnified; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexKNNQuery; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexRangeQuery; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MkTreeRKNNQuery; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; @@ -109,7 +110,7 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im } @Override - public void insert(DBID id) { + public void insert(DBIDRef id) { throw new UnsupportedOperationException("Insertion of single objects is not supported!"); } @@ -117,7 +118,7 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im public void insertAll(DBIDs ids) { List<MkTabEntry<D>> objs = new ArrayList<MkTabEntry<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } @@ -132,7 +133,7 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im * implemented yet. */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } @@ -170,7 +171,7 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexKNNQuery<O, S>(idx, dq); + return MTreeQueryUtil.getKNNQuery(idx, dq, hints); } @SuppressWarnings("unchecked") @@ -195,7 +196,7 @@ public class MkTabTreeIndex<O, D extends Distance<D>> extends MkTabTree<O, D> im } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexRangeQuery<O, S>(idx, dq); + return MTreeQueryUtil.getRangeQuery(idx, dq); } @SuppressWarnings("unchecked") diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java index 80955b8a..4276329c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTree.java @@ -55,7 +55,7 @@ public class MTree<O, D extends Distance<D>> extends AbstractMTree<O, D, MTreeNo /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(MTree.class); + private static final Logging LOG = Logging.getLogger(MTree.class); /** * Constructor. @@ -81,7 +81,7 @@ public class MTree<O, D extends Distance<D>> extends AbstractMTree<O, D, MTreeNo int distanceSize = exampleLeaf.getParentDistance().externalizableSize(); // FIXME: simulate a proper feature size! - int featuresize = 0; // DatabaseUtil.dimensionality(relation); + int featuresize = 0; // RelationUtil.dimensionality(relation); // overhead = index(4), numEntries(4), id(4), isLeaf(0.125) double overhead = 12.125; @@ -103,7 +103,7 @@ public class MTree<O, D extends Distance<D>> extends AbstractMTree<O, D, MTreeNo } if(dirCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); } // leafCapacity = (pageSize - overhead) / (objectID + parentDistance) + // 1 @@ -118,11 +118,11 @@ public class MTree<O, D extends Distance<D>> extends AbstractMTree<O, D, MTreeNo } if(leafCapacity < 10) { - logger.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); } - if(logger.isVerbose()) { - logger.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); + if(LOG.isVerbose()) { + LOG.verbose("Directory Capacity: " + (dirCapacity - 1) + "\nLeaf Capacity: " + (leafCapacity - 1)); } } @@ -161,6 +161,6 @@ public class MTree<O, D extends Distance<D>> extends AbstractMTree<O, D, MTreeNo @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java index 2567f81f..5c5aac04 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeFactory.java @@ -30,7 +30,6 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeFactor import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; /** * Factory for a M-Tree @@ -75,11 +74,6 @@ public class MTreeFactory<O, D extends Distance<D>> extends AbstractMTreeFactory */ public static class Parameterizer<O, D extends Distance<D>> extends AbstractMTreeFactory.Parameterizer<O, D> { @Override - protected void makeOptions(Parameterization config) { - super.makeOptions(config); - } - - @Override protected MTreeFactory<O, D> makeInstance() { return new MTreeFactory<O, D>(fileName, pageSize, cacheSize, distanceFunction); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java index fe60c04d..8afe1f2a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mtree/MTreeIndex.java @@ -28,6 +28,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; @@ -41,8 +43,7 @@ import de.lmu.ifi.dbs.elki.index.RangeIndex; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeLeafEntry; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexKNNQuery; -import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MetricalIndexRangeQuery; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query.MTreeQueryUtil; import de.lmu.ifi.dbs.elki.persistent.PageFile; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; @@ -82,15 +83,15 @@ public class MTreeIndex<O, D extends Distance<D>> extends MTree<O, D> implements } @Override - public void insert(DBID id) { - insert(createNewLeafEntry(id, relation.get(id), getDistanceFactory().undefinedDistance()), false); + public void insert(DBIDRef id) { + insert(createNewLeafEntry(DBIDUtil.deref(id), relation.get(id), getDistanceFactory().undefinedDistance()), false); } @Override public void insertAll(DBIDs ids) { List<MTreeEntry<D>> objs = new ArrayList<MTreeEntry<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); final O object = relation.get(id); objs.add(createNewLeafEntry(id, object, getDistanceFactory().undefinedDistance())); } @@ -105,7 +106,7 @@ public class MTreeIndex<O, D extends Distance<D>> extends MTree<O, D> implements * implemented yet. */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } @@ -143,7 +144,7 @@ public class MTreeIndex<O, D extends Distance<D>> extends MTree<O, D> implements } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexKNNQuery<O, S>(idx, dq); + return MTreeQueryUtil.getKNNQuery(idx, dq, hints); } @SuppressWarnings("unchecked") @@ -168,7 +169,7 @@ public class MTreeIndex<O, D extends Distance<D>> extends MTree<O, D> implements } AbstractMTree<O, S, ?, ?> idx = (AbstractMTree<O, S, ?, ?>) this; DistanceQuery<O, S> dq = distanceFunction.instantiate(relation); - return new MetricalIndexRangeQuery<O, S>(idx, dq); + return MTreeQueryUtil.getRangeQuery(idx, dq); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java new file mode 100644 index 00000000..52f777ba --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexKNNQuery.java @@ -0,0 +1,155 @@ +package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 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.List; + +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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; +import de.lmu.ifi.dbs.elki.index.tree.query.DoubleMTreeDistanceSearchCandidate; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; +import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; + +/** + * Instance of a KNN query for a particular spatial index. + * + * @author Erich Schubert + * + * @apiviz.uses AbstractMTree + * + * @param <O> Object type + */ +public class DoubleDistanceMetricalIndexKNNQuery<O> extends AbstractDistanceKNNQuery<O, DoubleDistance> { + /** + * The index to use + */ + protected final AbstractMTree<O, DoubleDistance, ?, ?> index; + + /** + * Distance function + */ + protected PrimitiveDoubleDistanceFunction<? super O> distf; + + /** + * Constructor. + * + * @param index Index to use + * @param distanceQuery Distance query used + * @param distf Distance function + */ + public DoubleDistanceMetricalIndexKNNQuery(AbstractMTree<O, DoubleDistance, ?, ?> index, DistanceQuery<O, DoubleDistance> distanceQuery, PrimitiveDoubleDistanceFunction<? super O> distf) { + super(distanceQuery); + this.index = index; + this.distf = distf; + } + + @Override + public KNNResult<DoubleDistance> getKNNForObject(O q, int k) { + if (k < 1) { + throw new IllegalArgumentException("At least one object has to be requested!"); + } + + DoubleDistanceKNNHeap knnList = new DoubleDistanceKNNHeap(k); + double d_k = Double.POSITIVE_INFINITY; + + final Heap<DoubleMTreeDistanceSearchCandidate> pq = new Heap<DoubleMTreeDistanceSearchCandidate>(); + + // Push the root node + pq.add(new DoubleMTreeDistanceSearchCandidate(0, index.getRootID(), null, 0)); + + // search in tree + while (!pq.isEmpty()) { + DoubleMTreeDistanceSearchCandidate pqNode = pq.poll(); + DBID id_p = pqNode.routingObjectID; + double d1 = pqNode.routingDistance; + + if (knnList.size() >= k && pqNode.mindist > d_k) { + break; + } + + AbstractMTreeNode<?, DoubleDistance, ?, ?> node = index.getNode(pqNode.nodeID); + + // directory node + if (!node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { + final MTreeEntry<DoubleDistance> entry = node.getEntry(i); + final DBID id_i = entry.getRoutingObjectID(); + double or_i = entry.getCoveringRadius().doubleValue(); + double d2 = id_p != null ? entry.getParentDistance().doubleValue() : 0; + double diff = Math.abs(d1 - d2); + + if (diff <= d_k + or_i) { + final O ob_i = relation.get(id_i); + double d3 = distf.doubleDistance(ob_i, q); + double d_min = Math.max(d3 - or_i, 0); + if (d_min <= d_k) { + pq.add(new DoubleMTreeDistanceSearchCandidate(d_min, ((DirectoryEntry) entry).getPageID(), id_i, d3)); + } + } + } + } + // data node + else { + for (int i = 0; i < node.getNumEntries(); i++) { + final MTreeEntry<DoubleDistance> entry = node.getEntry(i); + final DBID id_i = entry.getRoutingObjectID(); + double d2 = id_p != null ? entry.getParentDistance().doubleValue() : 0; + double diff = Math.abs(d1 - d2); + + if (diff <= d_k) { + final O o_i = relation.get(id_i); + double d3 = distf.doubleDistance(o_i, q); + if (d3 <= d_k) { + knnList.add(d3, id_i); + d_k = knnList.doubleKNNDistance(); + } + } + } + } + } + return knnList.toKNNList(); + } + + @Override + public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { + return getKNNForObject(relation.get(id), k); + } + + @Override + public List<KNNResult<DoubleDistance>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + // TODO: implement + throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java new file mode 100644 index 00000000..c3680111 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/DoubleDistanceMetricalIndexRangeQuery.java @@ -0,0 +1,135 @@ +package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 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 de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.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.metrical.mtreevariants.AbstractMTree; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; + +/** + * Instance of a range query for a particular spatial index. + * + * @author Erich Schubert + * + * @apiviz.uses AbstractMTree + */ +public class DoubleDistanceMetricalIndexRangeQuery<O> extends AbstractDistanceRangeQuery<O, DoubleDistance> { + /** + * The index to use + */ + protected final AbstractMTree<O, DoubleDistance, ?, ?> index; + + /** + * Distance function + */ + protected PrimitiveDoubleDistanceFunction<? super O> distf; + + /** + * Constructor. + * + * @param index Index to use + * @param distanceQuery Distance query used + * @param distf Distance function + */ + public DoubleDistanceMetricalIndexRangeQuery(AbstractMTree<O, DoubleDistance, ?, ?> index, DistanceQuery<O, DoubleDistance> distanceQuery, PrimitiveDoubleDistanceFunction<? super O> distf) { + super(distanceQuery); + this.index = index; + this.distf = distf; + } + + /** + * Performs a range query on the specified subtree. It recursively traverses + * all paths from the specified node, which cannot be excluded from leading to + * qualifying objects. + * + * @param id_p the routing object of the specified node + * @param node the root of the subtree to be traversed + * @param q the query object + * @param r_q the query range + * @param result the list holding the query results + */ + private void doRangeQuery(DBID id_p, AbstractMTreeNode<O, DoubleDistance, ?, ?> node, O q, double r_q, DoubleDistanceDBIDList result) { + final O o_p = id_p != null ? relation.get(id_p) : null; + double d1 = id_p != null ? distf.doubleDistance(o_p, q) : 0; + if (!node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { + MTreeEntry<DoubleDistance> entry = node.getEntry(i); + + double r_or = entry.getCoveringRadius().doubleValue(); + double d2 = id_p != null ? entry.getParentDistance().doubleValue() : 0; + double diff = Math.abs(d1 - d2); + + double sum = r_q + r_or; + + if (diff <= sum) { + DBID id_r = entry.getRoutingObjectID(); + double d3 = distf.doubleDistance(relation.get(id_r), q); + if (d3 <= sum) { + AbstractMTreeNode<O, DoubleDistance, ?, ?> child = index.getNode(((DirectoryEntry) entry).getPageID()); + doRangeQuery(id_r, child, q, r_q, result); + } + } + } + } else { + for (int i = 0; i < node.getNumEntries(); i++) { + MTreeEntry<DoubleDistance> entry = node.getEntry(i); + + double d2 = id_p != null ? entry.getParentDistance().doubleValue() : 0; + double diff = Math.abs(d1 - d2); + + if (diff <= r_q) { + DBID id_j = entry.getRoutingObjectID(); + O o_j = relation.get(id_j); + double d3 = distf.doubleDistance(o_j, q); + if (d3 <= r_q) { + result.add(d3, id_j); + } + } + } + } + } + + @Override + public DistanceDBIDResult<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { + final DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); + + doRangeQuery(null, index.getRoot(), obj, range.doubleValue(), result); + result.sort(); + return result; + } + + @Override + public DistanceDBIDResult<DoubleDistance> getRangeForDBID(DBIDRef id, DoubleDistance range) { + return getRangeForObject(relation.get(id), range); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java new file mode 100644 index 00000000..34980542 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MTreeQueryUtil.java @@ -0,0 +1,90 @@ +package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; + +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; +import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTree; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 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/>. + */ + +/** + * Query utility classes for MTrees. + * + * @author Erich Schubert + */ +public final class MTreeQueryUtil { + /** + * Get an RTree knn query, using an optimized double implementation when + * possible. + * + * @param <O> Object type + * @param <D> Distance type + * @param tree Tree to query + * @param distanceQuery distance query + * @param hints Optimizer hints + * @return Query object + */ + @SuppressWarnings({ "cast", "unchecked" }) + public static <O, D extends Distance<D>> KNNQuery<O, D> getKNNQuery(AbstractMTree<O, D, ?, ?> tree, DistanceQuery<O, D> distanceQuery, Object... hints) { + DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); + // Can we use an optimized query? + if(df instanceof PrimitiveDoubleDistanceFunction) { + PrimitiveDoubleDistanceFunction<? super O> dfc = (PrimitiveDoubleDistanceFunction<? super O>) df; + AbstractMTree<O, DoubleDistance, ?, ?> treec = (AbstractMTree<O, DoubleDistance, ?, ?>) tree; + DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) distanceQuery; + KNNQuery<O, ?> q = new DoubleDistanceMetricalIndexKNNQuery<O>(treec, dqc, dfc); + return (KNNQuery<O, D>) q; + } + return new MetricalIndexKNNQuery<O, D>(tree, distanceQuery); + } + + /** + * Get an RTree knn query, using an optimized double implementation when + * possible. + * + * @param <O> Object type + * @param <D> Distance type + * @param tree Tree to query + * @param distanceQuery distance query + * @param hints Optimizer hints + * @return Query object + */ + @SuppressWarnings({ "cast", "unchecked" }) + public static <O, D extends Distance<D>> RangeQuery<O, D> getRangeQuery(AbstractMTree<O, D, ?, ?> tree, DistanceQuery<O, D> distanceQuery, Object... hints) { + DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); + // Can we use an optimized query? + if(df instanceof PrimitiveDoubleDistanceFunction) { + PrimitiveDoubleDistanceFunction<? super O> dfc = (PrimitiveDoubleDistanceFunction<? super O>) df; + AbstractMTree<O, DoubleDistance, ?, ?> treec = (AbstractMTree<O, DoubleDistance, ?, ?>) tree; + DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) distanceQuery; + RangeQuery<O, ?> q = new DoubleDistanceMetricalIndexRangeQuery<O>(treec, dqc, dfc); + return (RangeQuery<O, D>) q; + } + return new MetricalIndexRangeQuery<O, D>(tree, distanceQuery); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java index c2450988..c2fafdae 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexKNNQuery.java @@ -24,15 +24,16 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; */ import java.util.List; -import java.util.Map; 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.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; +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.metrical.mtreevariants.AbstractMTree; @@ -40,8 +41,6 @@ import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.AbstractMTreeNode; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.MTreeEntry; import de.lmu.ifi.dbs.elki.index.tree.query.GenericMTreeDistanceSearchCandidate; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap; import de.lmu.ifi.dbs.elki.utilities.exceptions.ExceptionMessages; /** @@ -62,7 +61,7 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis /** * Constructor. - * + * * @param index Index to use * @param distanceQuery Distance query used */ @@ -71,70 +70,67 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis this.index = index; } - /** - * Performs a k-nearest neighbor query for the given FeatureVector with the - * given parameter k and the according distance function. The query result is - * in ascending order to the distance to the query object. - * - * @param q the id of the query object - * @param knnList the query result list - */ - protected final void doKNNQuery(O q, KNNHeap<D> knnList) { - final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new UpdatableHeap<GenericMTreeDistanceSearchCandidate<D>>(); + @Override + public KNNResult<D> getKNNForObject(O q, int k) { + if (k < 1) { + throw new IllegalArgumentException("At least one object has to be requested!"); + } - // push root - pq.add(new GenericMTreeDistanceSearchCandidate<D>(distanceQuery.nullDistance(), index.getRootID(), null)); + final D nullDistance = index.getDistanceFactory().nullDistance(); + KNNHeap<D> knnList = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k); D d_k = knnList.getKNNDistance(); + final Heap<GenericMTreeDistanceSearchCandidate<D>> pq = new Heap<GenericMTreeDistanceSearchCandidate<D>>(); + + // push root + pq.add(new GenericMTreeDistanceSearchCandidate<D>(nullDistance, index.getRootID(), null, nullDistance)); + // search in tree - while(!pq.isEmpty()) { + while (!pq.isEmpty()) { GenericMTreeDistanceSearchCandidate<D> pqNode = pq.poll(); - if(pqNode.mindist.compareTo(d_k) > 0) { - return; + if (knnList.size() >= k && pqNode.mindist.compareTo(d_k) > 0) { + break; } - AbstractMTreeNode<O, D, ?, ?> node = index.getNode(pqNode.nodeID); - DBID o_p = pqNode.routingObjectID; + AbstractMTreeNode<?, D, ?, ?> node = index.getNode(pqNode.nodeID); + DBID id_p = pqNode.routingObjectID; + D d1 = pqNode.routingDistance; // directory node - if(!node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { + if (!node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { MTreeEntry<D> entry = node.getEntry(i); DBID o_r = entry.getRoutingObjectID(); D r_or = entry.getCoveringRadius(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_r, o_p) : distanceQuery.nullDistance(); + D d2 = id_p != null ? entry.getParentDistance() : nullDistance; D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); D sum = d_k.plus(r_or); - if(diff.compareTo(sum) <= 0) { + if (diff.compareTo(sum) <= 0) { D d3 = distanceQuery.distance(o_r, q); - D d_min = DistanceUtil.max(d3.minus(r_or), distanceQuery.nullDistance()); - if(d_min.compareTo(d_k) <= 0) { - pq.add(new GenericMTreeDistanceSearchCandidate<D>(d_min, ((DirectoryEntry)entry).getPageID(), o_r)); + D d_min = DistanceUtil.max(d3.minus(r_or), index.getDistanceFactory().nullDistance()); + if (d_min.compareTo(d_k) <= 0) { + pq.add(new GenericMTreeDistanceSearchCandidate<D>(d_min, ((DirectoryEntry) entry).getPageID(), o_r, d3)); } } } - } - // data node else { - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { MTreeEntry<D> entry = node.getEntry(i); DBID o_j = entry.getRoutingObjectID(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_j, o_p) : distanceQuery.nullDistance(); + D d2 = id_p != null ? entry.getParentDistance() : nullDistance; - D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); + D diff = (d1.compareTo(d2) > 0) ? d1.minus(d2) : d2.minus(d1); - if(diff.compareTo(d_k) <= 0) { + if (diff.compareTo(d_k) <= 0) { D d3 = distanceQuery.distance(o_j, q); - if(d3.compareTo(d_k) <= 0) { + if (d3.compareTo(d_k) <= 0) { knnList.add(d3, o_j); d_k = knnList.getKNNDistance(); } @@ -142,16 +138,6 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis } } } - } - - @Override - public KNNResult<D> getKNNForObject(O obj, int k) { - if(k < 1) { - throw new IllegalArgumentException("At least one object has to be requested!"); - } - - final KNNHeap<D> knnList = new KNNHeap<D>(k, distanceQuery.getDistanceFactory().infiniteDistance()); - doKNNQuery(obj, knnList); return knnList.toKNNList(); } @@ -165,10 +151,4 @@ public class MetricalIndexKNNQuery<O, D extends Distance<D>> extends AbstractDis // TODO: implement throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } - - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - // TODO: implement - throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); - } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java index e2df2dc7..2ca19877 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MetricalIndexRangeQuery.java @@ -23,17 +23,12 @@ package de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; -import java.util.List; - import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; +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.metrical.mtreevariants.AbstractMTree; @@ -75,109 +70,47 @@ public class MetricalIndexRangeQuery<O, D extends Distance<D>> extends AbstractD * @param r_q the query range * @param result the list holding the query results */ - private void doRangeQuery(DBID o_p, AbstractMTreeNode<O, D, ?, ?> node, DBID q, D r_q, List<DistanceResultPair<D>> result) { - if(!node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { + private void doRangeQuery(DBID o_p, AbstractMTreeNode<O, D, ?, ?> node, O q, D r_q, GenericDistanceDBIDList<D> result) { + final D nullDistance = distanceQuery.nullDistance(); + D d1 = o_p != null ? distanceQuery.distance(o_p, q) : nullDistance; + if (!node.isLeaf()) { + for (int i = 0; i < node.getNumEntries(); i++) { MTreeEntry<D> entry = node.getEntry(i); DBID o_r = entry.getRoutingObjectID(); D r_or = entry.getCoveringRadius(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? entry.getParentDistance() : distanceQuery.nullDistance(); - // o_p != null ? distanceFunction.distance(o_r, o_p) :/ distanceFunction.nullDistance(); - + D d2 = o_p != null ? entry.getParentDistance() : nullDistance; D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); D sum = r_q.plus(r_or); - if(diff.compareTo(sum) <= 0) { + if (diff.compareTo(sum) <= 0) { D d3 = distanceQuery.distance(o_r, q); - if(d3.compareTo(sum) <= 0) { - AbstractMTreeNode<O, D, ?, ?> child = index.getNode(((DirectoryEntry)entry).getPageID()); + if (d3.compareTo(sum) <= 0) { + AbstractMTreeNode<O, D, ?, ?> child = index.getNode(((DirectoryEntry) entry).getPageID()); doRangeQuery(o_r, child, q, r_q, result); } } - } - } - - else { - for(int i = 0; i < node.getNumEntries(); i++) { + } else { + for (int i = 0; i < node.getNumEntries(); i++) { MTreeEntry<D> entry = node.getEntry(i); DBID o_j = entry.getRoutingObjectID(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_j, o_p) : distanceQuery.nullDistance(); + D d2 = o_p != null ? entry.getParentDistance() : nullDistance; D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); - if(diff.compareTo(r_q) <= 0) { + if (diff.compareTo(r_q) <= 0) { D d3 = distanceQuery.distance(o_j, q); - if(d3.compareTo(r_q) <= 0) { - DistanceResultPair<D> queryResult = new GenericDistanceResultPair<D>(d3, o_j); - result.add(queryResult); + if (d3.compareTo(r_q) <= 0) { + result.add(d3, o_j); } } } } } - /** - * Performs a range query on the specified subtree. It recursively traverses - * all paths from the specified node, which cannot be excluded from leading to - * qualifying objects. - * - * @param o_p the routing object of the specified node - * @param node the root of the subtree to be traversed - * @param q the id of the query object - * @param r_q the query range - * @param result the list holding the query results - */ - private void doRangeQuery(DBID o_p, AbstractMTreeNode<O, D, ?, ?> node, O q, D r_q, List<DistanceResultPair<D>> result) { - if(!node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - MTreeEntry<D> entry = node.getEntry(i); - DBID o_r = entry.getRoutingObjectID(); - - D r_or = entry.getCoveringRadius(); - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? entry.getParentDistance() : distanceQuery.nullDistance(); - // o_p != null ? distanceFunction.distance(o_r, o_p) : distanceFunction.nullDistance(); - - D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); - - D sum = r_q.plus(r_or); - - if(diff.compareTo(sum) <= 0) { - D d3 = distanceQuery.distance(o_r, q); - if(d3.compareTo(sum) <= 0) { - AbstractMTreeNode<O, D, ?, ?> child = index.getNode(((DirectoryEntry)entry).getPageID()); - doRangeQuery(o_r, child, q, r_q, result); - } - } - } - } - else { - for(int i = 0; i < node.getNumEntries(); i++) { - MTreeEntry<D> entry = node.getEntry(i); - DBID o_j = entry.getRoutingObjectID(); - - D d1 = o_p != null ? distanceQuery.distance(o_p, q) : distanceQuery.nullDistance(); - D d2 = o_p != null ? distanceQuery.distance(o_j, o_p) : distanceQuery.nullDistance(); - - D diff = d1.compareTo(d2) > 0 ? d1.minus(d2) : d2.minus(d1); - - if(diff.compareTo(r_q) <= 0) { - D d3 = distanceQuery.distance(o_j, q); - if(d3.compareTo(r_q) <= 0) { - DistanceResultPair<D> queryResult = new GenericDistanceResultPair<D>(d3, o_j); - result.add(queryResult); - } - } - } - } - } - @Override public DistanceDBIDResult<D> getRangeForObject(O obj, D range) { final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); @@ -185,7 +118,7 @@ public class MetricalIndexRangeQuery<O, D extends Distance<D>> extends AbstractD doRangeQuery(null, index.getRoot(), obj, range, result); // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } @@ -193,4 +126,4 @@ public class MetricalIndexRangeQuery<O, D extends Distance<D>> extends AbstractD 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/metrical/mtreevariants/query/MkTreeRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java index 067c3abe..e3f35c50 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/query/MkTreeRKNNQuery.java @@ -27,9 +27,9 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.AbstractRKNNQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -60,17 +60,17 @@ public class MkTreeRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQuery } @Override - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k) { + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k) { return index.reverseKNNQuery(id, k); } @Override - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends DistanceDBIDResult<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { // TODO: implement throw new UnsupportedOperationException(ExceptionMessages.UNSUPPORTED_NOT_YET); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleDistanceSearchCandidate.java b/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleDistanceSearchCandidate.java index 699c8290..1a3fc948 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleDistanceSearchCandidate.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleDistanceSearchCandidate.java @@ -23,10 +23,9 @@ package de.lmu.ifi.dbs.elki.index.tree.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ - - /** - * Candidate for expansion in a distance search (generic implementation). + * Candidate for expansion in a distance search (double optimized + * implementation). * * @author Erich Schubert */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleMTreeDistanceSearchCandidate.java b/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleMTreeDistanceSearchCandidate.java new file mode 100644 index 00000000..c26ac801 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/query/DoubleMTreeDistanceSearchCandidate.java @@ -0,0 +1,62 @@ +package de.lmu.ifi.dbs.elki.index.tree.query; + +/* + 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 de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * Encapsulates the attributes for a object that can be stored in a heap. The + * object to be stored represents a node in a M-Tree and some additional + * information. Additionally to the regular expansion candidate, this object + * holds the id of the routing object of the underlying M-Tree node and its + * covering radius. + * + * @author Elke Achtert + */ +public class DoubleMTreeDistanceSearchCandidate extends DoubleDistanceSearchCandidate { + /** + * The id of the routing object. + */ + public DBID routingObjectID; + + /** + * The distance from the query object to the routing object + */ + public double routingDistance; + + /** + * Creates a new heap node with the specified parameters. + * + * @param mindist the minimum distance of the node + * @param nodeID the id of the node + * @param routingObjectID the id of the routing object of the node + * @param routingDistance the distance from the query object to the query + * object + */ + public DoubleMTreeDistanceSearchCandidate(final double mindist, final Integer nodeID, final DBID routingObjectID, double routingDistance) { + super(mindist, nodeID); + this.routingObjectID = routingObjectID; + this.routingDistance = routingDistance; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/query/GenericMTreeDistanceSearchCandidate.java b/src/de/lmu/ifi/dbs/elki/index/tree/query/GenericMTreeDistanceSearchCandidate.java index e7fc0b19..94335860 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/query/GenericMTreeDistanceSearchCandidate.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/query/GenericMTreeDistanceSearchCandidate.java @@ -42,6 +42,11 @@ public class GenericMTreeDistanceSearchCandidate<D extends Distance<D>> extends * The id of the routing object. */ public DBID routingObjectID; + + /** + * The distance from the query to the routing object. + */ + public D routingDistance; /** * Creates a new heap node with the specified parameters. @@ -49,9 +54,11 @@ public class GenericMTreeDistanceSearchCandidate<D extends Distance<D>> extends * @param mindist the minimum distance of the node * @param nodeID the id of the node * @param routingObjectID the id of the routing object of the node + * @param routingDistance the distance from query to routing object */ - public GenericMTreeDistanceSearchCandidate(final D mindist, final Integer nodeID, final DBID routingObjectID) { + public GenericMTreeDistanceSearchCandidate(final D mindist, final Integer nodeID, final DBID routingObjectID, final D routingDistance) { super(mindist, nodeID); this.routingObjectID = routingObjectID; + this.routingDistance = routingDistance; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java index 0911a9c0..60981677 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java @@ -39,6 +39,9 @@ import de.lmu.ifi.dbs.elki.index.tree.AbstractLeafEntry; * @author Elke Achtert */ public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialEntry { + /** + * Serial version. + */ private static final long serialVersionUID = 1; /** @@ -65,17 +68,17 @@ public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialE } /** - * Constructor from number vector + * Constructor from number vector. * * @param id Object id * @param vector Number vector */ - public SpatialPointLeafEntry(DBID id, NumberVector<?, ?> vector) { + public SpatialPointLeafEntry(DBID id, NumberVector<?> vector) { super(id); int dim = vector.getDimensionality(); this.values = new double[dim]; for(int i = 0; i < dim; i++) { - values[i] = vector.doubleValue(i + 1); + values[i] = vector.doubleValue(i); } } @@ -84,20 +87,14 @@ public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialE return values.length; } - /** - * @return the value at the specified dimension - */ @Override public double getMin(int dimension) { - return values[dimension - 1]; + return values[dimension]; } - /** - * @return the value at the specified dimension - */ @Override public double getMax(int dimension) { - return values[dimension - 1]; + return values[dimension]; } /** diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java index 3bac751c..8ede52d7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java @@ -80,7 +80,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Development flag: This will enable some extra integrity checks on the tree. */ - protected final static boolean extraIntegrityChecks = false; + protected static final boolean EXTRA_INTEGRITY_CHECKS = false; /** * The height of this R*-Tree. @@ -93,7 +93,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E public int distanceCalcs = 0; /** - * The last inserted entry + * The last inserted entry. */ E lastInsertedEntry = null; @@ -103,27 +103,27 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E protected BulkSplit bulkSplitter; /** - * The split strategy + * The split strategy. */ protected SplitStrategy nodeSplitter = TopologicalSplitter.STATIC; /** - * The insertion strategy to use + * The insertion strategy to use. */ protected InsertionStrategy insertionStrategy = LeastOverlapInsertionStrategy.STATIC; /** - * Overflow treatment + * Overflow treatment. */ protected OverflowTreatment overflowTreatment = LimitedReinsertOverflowTreatment.RSTAR_OVERFLOW; /** - * Relative minimum fill + * Relative minimum fill. */ protected double relativeMinFill = 0.4; /** - * Constructor + * Constructor. * * @param pagefile Page file */ @@ -132,7 +132,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Set the bulk loading strategy + * Set the bulk loading strategy. * * @param bulkSplitter Bulk loading strategy */ @@ -155,7 +155,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Set insertion strategy + * Set insertion strategy. * * @param insertionStrategy the insertion strategy to set */ @@ -200,7 +200,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E N node = getNode(subtree.getLastPathComponent().getEntry()); if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { - if(((LeafEntry) node.getEntry(i)).getDBID().sameDBID(id)) { + if(DBIDUtil.equal(((LeafEntry) node.getEntry(i)).getDBID(), id)) { return subtree.pathByAddingChild(new TreeIndexPathComponent<E>(node.getEntry(i), i)); } } @@ -319,6 +319,8 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Initializes this R*-Tree from an existing persistent file. + * + * {@inheritDoc} */ @Override public void initializeFromFile(TreeIndexHeader header, PageFile<N> file) { @@ -327,7 +329,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E this.height = computeHeight(); if(getLogger().isDebugging()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append(getClass()); msg.append("\n height = ").append(height); getLogger().debugFine(msg.toString()); @@ -454,8 +456,10 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E /** * Performs a bulk load on this RTree with the specified data. Is called by * the constructor. + * + * @param entries Entries to bulk load */ - abstract protected void bulkLoad(List<E> entrys); + protected abstract void bulkLoad(List<E> entries); /** * Returns the height of this R*-Tree. @@ -480,7 +484,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * * @return the height of this RTree */ - abstract protected int computeHeight(); + protected abstract int computeHeight(); /** * Returns true if in the specified node an overflow occurred, false @@ -489,7 +493,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @param node the node to be tested for overflow * @return true if in the specified node an overflow occurred, false otherwise */ - abstract protected boolean hasOverflow(N node); + protected abstract boolean hasOverflow(N node); /** * Returns true if in the specified node an underflow occurred, false @@ -499,7 +503,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @return true if in the specified node an underflow occurred, false * otherwise */ - abstract protected boolean hasUnderflow(N node); + protected abstract boolean hasUnderflow(N node); /** * Creates a new directory entry representing the specified node. @@ -507,7 +511,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * @param node the node to be represented by the new entry * @return the newly created directory entry */ - abstract protected E createNewDirectoryEntry(N node); + protected abstract E createNewDirectoryEntry(N node); /** * Creates a new root node that points to the two specified child nodes and @@ -852,7 +856,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E // node is root else { - if(hasUnderflow(node) & node.getNumEntries() == 1 && !node.isLeaf()) { + if(hasUnderflow(node) && node.getNumEntries() == 1 && !node.isLeaf()) { N child = getNode(node.getEntry(0)); N newRoot; if(child.isLeaf()) { @@ -889,7 +893,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E } /** - * Determines the entries pointing to the leaf nodes of the specified subtree + * Determines the entries pointing to the leaf nodes of the specified subtree. * * @param node the subtree * @param result the result to store the ids in @@ -914,7 +918,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E * Perform additional integrity checks. */ public void doExtraIntegrityChecks() { - if(extraIntegrityChecks) { + if(EXTRA_INTEGRITY_CHECKS) { getRoot().integrityCheck(this); } } @@ -926,7 +930,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E */ @Override public String toString() { - StringBuffer result = new StringBuffer(); + StringBuilder result = new StringBuilder(); int dirNodes = 0; int leafNodes = 0; int objects = 0; @@ -964,7 +968,7 @@ public abstract class AbstractRStarTree<N extends AbstractRStarTreeNode<N, E>, E result.append(getClass().getName()).append(" has ").append((levels + 1)).append(" levels.\n"); result.append(dirNodes).append(" Directory Knoten (max = ").append(dirCapacity - 1).append(", min = ").append(dirMinimum).append(")\n"); result.append(leafNodes).append(" Daten Knoten (max = ").append(leafCapacity - 1).append(", min = ").append(leafMinimum).append(")\n"); - result.append(objects).append(" ").append(dim).append("-dim. Punkte im Baum \n"); + result.append(objects).append(' ').append(dim).append("-dim. Punkte im Baum \n"); PageFileUtil.appendPageFileStatistics(result, getPageFileStatistics()); } else { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java index e2bb3abb..ace5ad41 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java @@ -37,8 +37,8 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow. import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.SplitStrategy; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.TopologicalSplitter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint.IntervalBoundary; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -56,31 +56,31 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * @param <E> Entry type * @param <I> Index type */ -public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E> & Index> extends TreeIndexFactory<O, I> { +public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E> & Index> extends TreeIndexFactory<O, I> { /** * Fast-insertion parameter. Optional. */ - public static OptionID INSERTION_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insertionstrategy", "The strategy to use for object insertion."); + public static OptionID INSERTION_STRATEGY_ID = new OptionID("rtree.insertionstrategy", "The strategy to use for object insertion."); /** * Split strategy parameter. Optional. */ - public static OptionID SPLIT_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.splitstrategy", "The strategy to use for node splitting."); + public static OptionID SPLIT_STRATEGY_ID = new OptionID("rtree.splitstrategy", "The strategy to use for node splitting."); /** * Parameter for bulk strategy */ - public static final OptionID BULK_SPLIT_ID = OptionID.getOrCreateOptionID("spatial.bulkstrategy", "The class to perform the bulk split with."); + public static final OptionID BULK_SPLIT_ID = new OptionID("spatial.bulkstrategy", "The class to perform the bulk split with."); /** * Parameter for the relative minimum fill. */ - public static final OptionID MINIMUM_FILL_ID = OptionID.getOrCreateOptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); + public static final OptionID MINIMUM_FILL_ID = new OptionID("rtree.minimum-fill", "Minimum relative fill required for data pages."); /** * Overflow treatment. */ - public static OptionID OVERFLOW_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); + public static OptionID OVERFLOW_STRATEGY_ID = new OptionID("rtree.overflowtreatment", "The strategy to use for handling overflows."); /** * Strategy to find the insertion node with. @@ -140,7 +140,7 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e * * @apiviz.exclude */ - public static abstract class Parameterizer<O extends NumberVector<O, ?>> extends TreeIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O extends NumberVector<?>> extends TreeIndexFactory.Parameterizer<O> { /** * Insertion strategy */ @@ -170,19 +170,21 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e protected void makeOptions(Parameterization config) { super.makeOptions(config); ObjectParameter<InsertionStrategy> insertionStrategyP = new ObjectParameter<InsertionStrategy>(INSERTION_STRATEGY_ID, InsertionStrategy.class, CombinedInsertionStrategy.class); - if(config.grab(insertionStrategyP)) { + if (config.grab(insertionStrategyP)) { insertionStrategy = insertionStrategyP.instantiateClass(config); } ObjectParameter<SplitStrategy> splitStrategyP = new ObjectParameter<SplitStrategy>(SPLIT_STRATEGY_ID, SplitStrategy.class, TopologicalSplitter.class); - if(config.grab(splitStrategyP)) { + if (config.grab(splitStrategyP)) { nodeSplitter = splitStrategyP.instantiateClass(config); } - DoubleParameter minimumFillP = new DoubleParameter(MINIMUM_FILL_ID, new IntervalConstraint(0.0, IntervalBoundary.OPEN, 0.5, IntervalBoundary.OPEN), 0.4); + DoubleParameter minimumFillP = new DoubleParameter(MINIMUM_FILL_ID, 0.4); + minimumFillP.addConstraint(new GreaterConstraint(0.0)); + minimumFillP.addConstraint(new LessConstraint(0.5)); if (config.grab(minimumFillP)) { minimumFill = minimumFillP.getValue(); } ObjectParameter<OverflowTreatment> overflowP = new ObjectParameter<OverflowTreatment>(OVERFLOW_STRATEGY_ID, OverflowTreatment.class, LimitedReinsertOverflowTreatment.class); - if(config.grab(overflowP)) { + if (config.grab(overflowP)) { overflowTreatment = overflowP.instantiateClass(config); } configBulkLoad(config); @@ -195,7 +197,7 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e */ protected void configBulkLoad(Parameterization config) { ObjectParameter<BulkSplit> bulkSplitP = new ObjectParameter<BulkSplit>(BULK_SPLIT_ID, BulkSplit.class, true); - if(config.grab(bulkSplitP)) { + if (config.grab(bulkSplitP)) { bulkSplitter = bulkSplitP.instantiateClass(config); } } @@ -203,4 +205,4 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<O, ?>, N e @Override protected abstract AbstractRStarTreeFactory<O, ?, ?, ?> makeInstance(); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java index 46e3003e..80666ebb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java @@ -96,7 +96,7 @@ public abstract class AbstractRStarTreeNode<N extends AbstractRStarTreeNode<N, E if(se.hasMBR()) { final int dim = se.getDimensionality(); // Test for changes - for(int i = 1; i <= dim; i++) { + for(int i = 0; i < dim; i++) { if(Math.abs(se.getMin(i) - mbr.getMin(i)) > Float.MIN_NORMAL) { changed = true; break; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java index 41882ce2..fd7d3d8b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java @@ -120,7 +120,7 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E initialize(spatialObjects.get(0)); } - StringBuffer msg = getLogger().isDebuggingFine() ? new StringBuffer() : null; + StringBuilder msg = getLogger().isDebuggingFine() ? new StringBuilder() : null; // Tiny tree that fits into a single page if(spatialObjects.size() <= leafCapacity) { @@ -165,8 +165,8 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E } if(msg != null) { msg.append("\n height = ").append(getHeight()); - msg.append("\n root " + getRoot()); - getLogger().debugFine(msg.toString() + "\n"); + msg.append("\n root ").append(getRoot()); + getLogger().debugFine(msg.toString()); } } @@ -228,9 +228,9 @@ public abstract class NonFlatRStarTree<N extends AbstractRStarTreeNode<N, E>, E // write to file writeNode(root); if(getLogger().isDebuggingFiner()) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); msg.append("pageNo ").append(root.getPageID()); - getLogger().debugFiner(msg.toString() + "\n"); + getLogger().debugFiner(msg.toString()); } return root; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java index 9848f121..bc701185 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java @@ -29,23 +29,23 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; /** * Defines the requirements for a leaf entry in an DeLiClu-Tree node. - * Additionally to a leaf entry in an R*-Tree two boolean flags that indicate whether this entry's node - * contains handled or unhandled data objects. - * + * Additionally to a leaf entry in an R*-Tree two boolean flags that indicate + * whether this entry's node contains handled or unhandled data objects. + * * @author Elke Achtert */ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEntry { private static final long serialVersionUID = 1; /** - * Indicates that the node (or its child nodes) which is represented by this entry - * contains handled data objects. + * Indicates that the node (or its child nodes) which is represented by this + * entry contains handled data objects. */ private boolean hasHandled; /** - * Indicates that the node (or its child nodes) which is represented by this entry - * contains unhandled data objects. + * Indicates that the node (or its child nodes) which is represented by this + * entry contains unhandled data objects. */ private boolean hasUnhandled; @@ -53,16 +53,16 @@ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEn * Empty constructor for serialization purposes. */ public DeLiCluLeafEntry() { - // empty constructor + // empty constructor } /** * Constructs a new LeafEntry object with the given parameters. - * - * @param id the unique id of the underlying data object + * + * @param id the unique id of the underlying data object * @param vector the vector to store */ - public DeLiCluLeafEntry(DBID id, NumberVector<?,?> vector) { + public DeLiCluLeafEntry(DBID id, NumberVector<?> vector) { super(id, vector); this.hasHandled = false; this.hasUnhandled = true; @@ -90,7 +90,7 @@ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEn /** * Returns the id as a string representation of this entry. - * + * * @return a string representation of this entry */ @Override diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java index 6f4f782d..0cd74a14 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java @@ -48,7 +48,7 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(DeLiCluTree.class); + private static final Logging LOG = Logging.getLogger(DeLiCluTree.class); /** * Holds the ids of the expanded nodes. @@ -168,6 +168,6 @@ public class DeLiCluTree extends NonFlatRStarTree<DeLiCluNode, DeLiCluEntry> { @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java index 3f9627a9..b64192c1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java @@ -42,7 +42,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class DeLiCluTreeFactory<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>> { +public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>> { /** * Constructor. * @@ -82,7 +82,7 @@ public class DeLiCluTreeFactory<O extends NumberVector<O, ?>> extends AbstractRS * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { @Override protected DeLiCluTreeFactory<O> makeInstance() { return new DeLiCluTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java index dd3b4d6b..b1216a51 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java @@ -29,6 +29,8 @@ import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -52,9 +54,9 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @param <O> Object type */ -public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O> { +public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O> { /** - * The relation we index + * The relation we index. */ private Relation<O> relation; @@ -73,7 +75,7 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree /** * The appropriate logger for this index. */ - private static final Logging logger = Logging.getLogger(DeLiCluTreeIndex.class); + private static final Logging LOG = Logging.getLogger(DeLiCluTreeIndex.class); /** * Creates a new leaf entry representing the specified data object. @@ -93,14 +95,14 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * @return the path of node ids from the root to the objects's parent */ public synchronized List<TreeIndexPathComponent<DeLiCluEntry>> setHandled(DBID id, O obj) { - if(logger.isDebugging()) { - logger.debugFine("setHandled " + id + ", " + obj + "\n"); + if (LOG.isDebugging()) { + LOG.debugFine("setHandled " + id + ", " + obj + "\n"); } // find the leaf node containing o IndexTreePath<DeLiCluEntry> pathToObject = findPathToObject(getRootPath(), obj, id); - if(pathToObject == null) { + if (pathToObject == null) { throw new AbortException("Object not found in setHandled."); } @@ -109,12 +111,12 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree entry.setHasHandled(true); entry.setHasUnhandled(false); - for(IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { + for (IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { DeLiCluEntry parentEntry = path.getParentPath().getLastPathComponent().getEntry(); DeLiCluNode node = getNode(parentEntry); boolean hasHandled = false; boolean hasUnhandled = false; - for(int i = 0; i < node.getNumEntries(); i++) { + for (int i = 0; i < node.getNumEntries(); i++) { final DeLiCluEntry nodeEntry = node.getEntry(i); hasHandled = hasHandled || nodeEntry.hasHandled(); hasUnhandled = hasUnhandled || nodeEntry.hasUnhandled(); @@ -132,8 +134,8 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * @param id the object id that was inserted */ @Override - public final void insert(DBID id) { - insertLeaf(createNewLeafEntry(id)); + public final void insert(DBIDRef id) { + insertLeaf(createNewLeafEntry(DBIDUtil.deref(id))); } /** @@ -144,21 +146,20 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree */ @Override public final void insertAll(DBIDs ids) { - if(ids.isEmpty() || (ids.size() == 1)) { + if (ids.isEmpty() || (ids.size() == 1)) { return; } // Make an example leaf - if(canBulkLoad()) { + if (canBulkLoad()) { List<DeLiCluEntry> leafs = new ArrayList<DeLiCluEntry>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - leafs.add(createNewLeafEntry(iter.getDBID())); + leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); } bulkLoad(leafs); - } - else { + } else { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - insert(iter.getDBID()); + insert(iter); } } @@ -172,11 +173,11 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree * false otherwise */ @Override - public final boolean delete(DBID id) { + public final boolean delete(DBIDRef id) { // find the leaf node containing o O obj = relation.get(id); IndexTreePath<DeLiCluEntry> deletionPath = findPathToObject(getRootPath(), obj, id); - if(deletionPath == null) { + if (deletionPath == null) { return false; } deletePath(deletionPath); @@ -186,18 +187,18 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override public void deleteAll(DBIDs ids) { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - delete(iter.getDBID()); + delete(DBIDUtil.deref(iter)); } } @Override public <D extends Distance<D>> RangeQuery<O, D> getRangeQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { // Query on the relation we index - if(distanceQuery.getRelation() != relation) { + if (distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if(!(distanceQuery instanceof SpatialDistanceQuery)) { + if (!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; @@ -207,11 +208,11 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override public <D extends Distance<D>> KNNQuery<O, D> getKNNQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { // Query on the relation we index - if(distanceQuery.getRelation() != relation) { + if (distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if(!(distanceQuery instanceof SpatialDistanceQuery)) { + if (!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; @@ -230,6 +231,6 @@ public class DeLiCluTreeIndex<O extends NumberVector<?, ?>> extends DeLiCluTree @Override protected Logging getLogger() { - return logger; + return LOG; } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java index f0acc233..6d539f25 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java @@ -38,11 +38,11 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -51,7 +51,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -102,8 +101,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param object the query object * @param knnList the knn list containing the result */ - protected void doKNNQuery(O object, KNNHeap<DoubleDistance> knnList) { - final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() * 2, 20)); + protected void doKNNQuery(O object, DoubleDistanceKNNHeap knnList) { + final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new DoubleDistanceSearchCandidate(0.0, tree.getRootID())); @@ -120,7 +119,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } } - private double expandNode(O object, KNNHeap<DoubleDistance> knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final Integer nodeID) { + private double expandNode(O object, DoubleDistanceKNNHeap knnList, final Heap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -129,8 +128,8 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend double distance = distanceFunction.doubleMinDist(entry, object); tree.distanceCalcs++; if(distance <= maxDist) { - knnList.add(new DoubleDistanceResultPair(distance, ((LeafEntry) entry).getDBID())); - maxDist = knnList.getKNNDistance().doubleValue(); + knnList.add(distance, ((LeafEntry) entry).getDBID()); + maxDist = knnList.doubleKNNDistance(); } } } @@ -160,20 +159,20 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param node the node for which the query should be performed * @param knnLists a map containing the knn lists for each query objects */ - protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap<DoubleDistance>> knnLists) { + protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, DoubleDistanceKNNHeap> knnLists) { if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry p = node.getEntry(i); - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { final DBID q = ent.getKey(); - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - DoubleDistance knn_q_maxDist = knns_q.getKNNDistance(); + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); DBID pid = ((LeafEntry) p).getDBID(); // FIXME: objects are NOT accessible by DBID in a plain rtree context! - DoubleDistance dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q)); + double dist_pq = distanceFunction.doubleDistance(relation.get(pid), relation.get(q)); tree.distanceCalcs++; - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { + if(dist_pq <= knn_q_maxDist) { knns_q.add(dist_pq, pid); } } @@ -187,13 +186,13 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend List<DoubleDistanceEntry> entries = getSortedEntries(node, ids); for(DoubleDistanceEntry distEntry : entries) { double minDist = distEntry.distance; - for(Entry<DBID, KNNHeap<DoubleDistance>> ent : knnLists.entrySet()) { - final KNNHeap<DoubleDistance> knns_q = ent.getValue(); - double knn_q_maxDist = knns_q.getKNNDistance().doubleValue(); + for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { + final DoubleDistanceKNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.doubleKNNDistance(); if(minDist <= knn_q_maxDist) { SpatialEntry entry = distEntry.entry; - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -264,47 +263,41 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } @Override - public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { + public DoubleDistanceKNNList getKNNForObject(O obj, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final KNNHeap<DoubleDistance> knnList = new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance()); + final DoubleDistanceKNNHeap knnList = new DoubleDistanceKNNHeap(k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @Override - public KNNResult<DoubleDistance> getKNNForDBID(DBIDRef id, int k) { + public DoubleDistanceKNNList getKNNForDBID(DBIDRef id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<KNNResult<DoubleDistance>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<DoubleDistanceKNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } // While this works, it seems to be slow at least for large sets! - final Map<DBID, KNNHeap<DoubleDistance>> knnLists = new HashMap<DBID, KNNHeap<DoubleDistance>>(ids.size()); + final Map<DBID, DoubleDistanceKNNHeap> knnLists = new HashMap<DBID, DoubleDistanceKNNHeap>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - knnLists.put(id, new KNNHeap<DoubleDistance>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + DBID id = DBIDUtil.deref(iter); + knnLists.put(id, new DoubleDistanceKNNHeap(k)); } batchNN(tree.getRoot(), knnLists); - List<KNNResult<DoubleDistance>> result = new ArrayList<KNNResult<DoubleDistance>>(); + List<DoubleDistanceKNNList> result = new ArrayList<DoubleDistanceKNNList>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); + DBID id = DBIDUtil.deref(iter); result.add(knnLists.get(id).toKNNList()); } return result; } - - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<DoubleDistance>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java index 1a861c3e..715b9552 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java @@ -23,16 +23,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -90,8 +87,8 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<DoubleDistance> doRangeQuery(O object, double epsilon) { - final GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + protected DoubleDistanceDBIDList doRangeQuery(O object, double epsilon) { + final DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); final Heap<DoubleDistanceSearchCandidate> pq = new Heap<DoubleDistanceSearchCandidate>(); // push root @@ -104,7 +101,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -113,7 +110,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte if(distance <= epsilon) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new DoubleDistanceResultPair(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -124,7 +121,7 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java index 09ebb61a..ed7f5949 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java @@ -40,9 +40,11 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.DistanceEntry; @@ -52,7 +54,6 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -103,7 +104,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis * @param knnList the knn list containing the result */ protected void doKNNQuery(O object, KNNHeap<D> knnList) { - final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() * 2, 20)); + final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(Math.min(knnList.getK() << 1, 20)); // push root pq.add(new GenericDistanceSearchCandidate<D>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); @@ -120,7 +121,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final Integer nodeID) { + private D expandNode(O object, KNNHeap<D> knnList, final Heap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { @@ -192,7 +193,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis if(minDist.compareTo(knn_q_maxDist) <= 0) { SpatialEntry entry = distEntry.getEntry(); - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID()); + AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); batchNN(child, knnLists); break; } @@ -201,12 +202,6 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis } } - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - AbstractRStarTreeNode<?, ?> root = tree.getRoot(); - batchNN(root, heaps); - } - /** * Sorts the entries of the specified node according to their minimum distance * to the specified objects. @@ -238,7 +233,7 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis throw new IllegalArgumentException("At least one enumeration has to be requested!"); } - final KNNHeap<D> knnList = new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance()); + final KNNHeap<D> knnList = KNNUtil.newHeap(distanceFunction, k); doKNNQuery(obj, knnList); return knnList.toKNNList(); } @@ -256,14 +251,14 @@ public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Dis // While this works, it seems to be slow at least for large sets! final Map<DBID, KNNHeap<D>> knnLists = new HashMap<DBID, KNNHeap<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - knnLists.put(iter.getDBID(), new KNNHeap<D>(k, distanceFunction.getDistanceFactory().infiniteDistance())); + knnLists.put(DBIDUtil.deref(iter), KNNUtil.newHeap(distanceFunction, k)); } batchNN(tree.getRoot(), knnLists); List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - result.add(knnLists.get(iter.getDBID()).toKNNList()); + result.add(knnLists.get(DBIDUtil.deref(iter)).toKNNList()); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java index 3b312ed7..a5232b30 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java @@ -23,16 +23,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; @@ -89,7 +86,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D * @param epsilon Query range * @return Objects contained in query range. */ - protected GenericDistanceDBIDList<D> doRangeQuery(O object, D epsilon) { + protected DistanceDBIDResult<D> doRangeQuery(O object, D epsilon) { final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<D>(); final Heap<GenericDistanceSearchCandidate<D>> pq = new Heap<GenericDistanceSearchCandidate<D>>(); @@ -103,7 +100,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D break; } - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID.intValue()); final int numEntries = node.getNumEntries(); for(int i = 0; i < numEntries; i++) { @@ -111,7 +108,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D if(distance.compareTo(epsilon) <= 0) { if(node.isLeaf()) { LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(new GenericDistanceResultPair<D>(distance, entry.getDBID())); + result.add(distance, entry.getDBID()); } else { DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); @@ -122,7 +119,7 @@ public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends D } // sort the result according to the distances - Collections.sort(result); + result.sort(); return result; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java index 53b32c6b..d63d77cb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java @@ -48,7 +48,7 @@ public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(RStarTree.class); + private static final Logging LOG = Logging.getLogger(RStarTree.class); /** * Constructor. @@ -91,6 +91,6 @@ public class RStarTree extends NonFlatRStarTree<RStarTreeNode, SpatialEntry> { @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java index 79aac0bd..da7c03fd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java @@ -43,7 +43,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeFactory<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>> { +public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>> { /** * Constructor. * @@ -83,7 +83,7 @@ public class RStarTreeFactory<O extends NumberVector<O, ?>> extends AbstractRSta * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<O, ?>> extends AbstractRStarTreeFactory.Parameterizer<O> { + public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O> { @Override protected RStarTreeFactory<O> makeInstance() { return new RStarTreeFactory<O>(fileName, pageSize, cacheSize, bulkSplitter, insertionStrategy, nodeSplitter, overflowTreatment, minimumFill); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java index ab136926..1946293f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java @@ -27,8 +27,9 @@ import java.util.ArrayList; import java.util.List; import de.lmu.ifi.dbs.elki.data.NumberVector; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; @@ -52,11 +53,11 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree implements RangeIndex<O>, KNNIndex<O> { +public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree implements RangeIndex<O>, KNNIndex<O> { /** * The appropriate logger for this index. */ - private static final Logging logger = Logging.getLogger(RStarTreeIndex.class); + private static final Logging LOG = Logging.getLogger(RStarTreeIndex.class); /** * Relation @@ -81,8 +82,8 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * @param id Object id * @return Spatial leaf entry */ - protected SpatialPointLeafEntry createNewLeafEntry(DBID id) { - return new SpatialPointLeafEntry(id, relation.get(id)); + protected SpatialPointLeafEntry createNewLeafEntry(DBIDRef id) { + return new SpatialPointLeafEntry(DBIDUtil.deref(id), relation.get(id)); } /** @@ -91,7 +92,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * @param id the object id that was inserted */ @Override - public void insert(DBID id) { + public void insert(DBIDRef id) { insertLeaf(createNewLeafEntry(id)); } @@ -111,13 +112,13 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl if(canBulkLoad()) { List<SpatialEntry> leafs = new ArrayList<SpatialEntry>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - leafs.add(createNewLeafEntry(iter.getDBID())); + leafs.add(createNewLeafEntry(iter)); } bulkLoad(leafs); } else { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - insert(iter.getDBID()); + insert(DBIDUtil.deref(iter)); } } @@ -131,7 +132,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl * false otherwise */ @Override - public boolean delete(DBID id) { + public boolean delete(DBIDRef id) { // find the leaf node containing o O obj = relation.get(id); IndexTreePath<SpatialEntry> deletionPath = findPathToObject(getRootPath(), obj, id); @@ -145,7 +146,7 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl @Override public void deleteAll(DBIDs ids) { for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - delete(iter.getDBID()); + delete(iter); } } @@ -189,6 +190,6 @@ public class RStarTreeIndex<O extends NumberVector<?, ?>> extends RStarTree impl @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java index 90a8b622..2fd69531 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java @@ -45,7 +45,7 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { /** * Logger. */ - private static final Logging logger = Logging.getLogger(MaxExtensionBulkSplit.class); + private static final Logging LOG = Logging.getLogger(MaxExtensionBulkSplit.class); /** * Static instance @@ -74,12 +74,12 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { List<N> objects = new ArrayList<N>(spatialObjects); while(objects.size() > 0) { - StringBuffer msg = new StringBuffer(); + StringBuilder msg = new StringBuilder(); // get the split axis and split point int splitAxis = chooseMaximalExtendedSplitAxis(objects); int splitPoint = chooseBulkSplitPoint(objects.size(), minEntries, maxEntries); - if(logger.isDebugging()) { + if(LOG.isDebugging()) { msg.append("\nsplitAxis ").append(splitAxis); msg.append("\nsplitPoint ").append(splitPoint); } @@ -96,15 +96,15 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { partitions.add(partition1); // copy array - if(logger.isDebugging()) { - msg.append("\ncurrent partition " + partition1); + if(LOG.isDebugging()) { + msg.append("\ncurrent partition ").append(partition1); msg.append("\nremaining objects # ").append(objects.size()); - logger.debugFine(msg.toString()); + LOG.debugFine(msg.toString()); } } - if(logger.isDebugging()) { - logger.debugFine("partitions " + partitions); + if(LOG.isDebugging()) { + LOG.debugFine("partitions " + partitions); } return partitions; } @@ -125,17 +125,17 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { // compute min and max value in each dimension for(SpatialComparable object : objects) { - for(int d = 1; d <= dimension; d++) { + for(int d = 0; d < dimension; d++) { double min, max; min = object.getMin(d); max = object.getMax(d); - if(maxExtension[d - 1] < max) { - maxExtension[d - 1] = max; + if(maxExtension[d] < max) { + maxExtension[d] = max; } - if(minExtension[d - 1] > min) { - minExtension[d - 1] = min; + if(minExtension[d] > min) { + minExtension[d] = min; } } } @@ -143,8 +143,8 @@ public class MaxExtensionBulkSplit extends AbstractBulkSplit { // set split axis to dim with maximal extension int splitAxis = -1; double max = 0; - for(int d = 1; d <= dimension; d++) { - double currentExtension = maxExtension[d - 1] - minExtension[d - 1]; + for(int d = 0; d < dimension; d++) { + double currentExtension = maxExtension[d] - minExtension[d]; if(max < currentExtension) { max = currentExtension; splitAxis = d; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java index b99ae01e..2209ddef 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java @@ -45,7 +45,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @Reference(authors = "Roussopoulos, N. and Leifker, D.", title = "Direct spatial search on pictorial databases using packed R-trees", booktitle = "ACM SIGMOD Record 14-4", url = "http://dx.doi.org/10.1145/971699.318900") public class OneDimSortBulkSplit extends AbstractBulkSplit { /** - * Static instance + * Static instance. */ public static final AbstractBulkSplit STATIC = new OneDimSortBulkSplit(); @@ -62,8 +62,8 @@ public class OneDimSortBulkSplit extends AbstractBulkSplit { Collections.sort(spatialObjects, new Comparator<SpatialComparable>() { @Override public int compare(SpatialComparable o1, SpatialComparable o2) { - double min1 = (o1.getMax(1) + o1.getMin(1)) / 2; - double min2 = (o2.getMax(1) + o2.getMin(1)) / 2; + double min1 = (o1.getMax(0) + o1.getMin(0)) * .5; + double min2 = (o2.getMax(0) + o2.getMin(0)) * .5; return Double.compare(min1, min2); } }); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java index 28e96da6..e24ef3ce 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java @@ -59,15 +59,15 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { * * @param objs Object list * @param start Subinterval start - * @param end Subinteval end + * @param end Subinterval end * @param depth Iteration depth (must be less than dimensionality!) * @param dims Total number of dimensions * @param maxEntries Maximum page size * @param c Comparison helper * @param ret Output list + * @param <T> data type */ protected <T extends SpatialComparable> void strPartition(List<T> objs, int start, int end, int depth, int dims, int maxEntries, Compare<T> c, List<List<T>> ret) { - c.dim = depth + 1; final int p = (int) Math.ceil((end - start) / (double) maxEntries); final int s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); @@ -78,6 +78,7 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { int e2 = start + (int) (((i + 1) * len) / s); // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); if(e2 < end) { + c.dim = depth; QuickSelect.quickSelect(objs, c, s2, end, e2); } if(depth + 1 == dims) { @@ -101,9 +102,9 @@ public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { */ private static class Compare<T extends SpatialComparable> implements Comparator<T> { /** - * Current dimension + * Current dimension. */ - public int dim; + int dim; @Override public int compare(T o1, T o2) { diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java index 9c3a41a1..beb6e657 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java @@ -82,7 +82,7 @@ public class SpatialSortBulkSplit extends AbstractBulkSplit { /** * Option ID for spatial sorting */ - public static final OptionID SORTER_ID = OptionID.getOrCreateOptionID("rtree.bulk.spatial-sort", "Strategy for spatial sorting in bulk loading."); + public static final OptionID SORTER_ID = new OptionID("rtree.bulk.spatial-sort", "Strategy for spatial sorting in bulk loading."); /** * Sorting class diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java index a1dfbdb0..c39bd914 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java @@ -144,7 +144,7 @@ public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInse /** * Fast-insertion parameter. Optional. */ - public static OptionID INSERTION_CANDIDATES_ID = OptionID.getOrCreateOptionID("rtree.insertion-candidates", "defines how many children are tested for finding the child generating the least overlap when inserting an object."); + public static OptionID INSERTION_CANDIDATES_ID = new OptionID("rtree.insertion-candidates", "defines how many children are tested for finding the child generating the least overlap when inserting an object."); /** * The number of candidates to use @@ -154,7 +154,8 @@ public class ApproximativeLeastOverlapInsertionStrategy extends LeastOverlapInse @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - IntParameter insertionCandidatesP = new IntParameter(INSERTION_CANDIDATES_ID, new GreaterConstraint(0), numCandidates); + IntParameter insertionCandidatesP = new IntParameter(INSERTION_CANDIDATES_ID, numCandidates); + insertionCandidatesP.addConstraint(new GreaterConstraint(0)); if(config.grab(insertionCandidatesP)) { numCandidates = insertionCandidatesP.getValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java index c90d99b2..63bbe9dc 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java @@ -88,12 +88,12 @@ public class CombinedInsertionStrategy implements InsertionStrategy { /** * Insertion strategy for directory nodes. */ - public static final OptionID DIR_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insert-directory", "Insertion strategy for directory nodes."); + public static final OptionID DIR_STRATEGY_ID = new OptionID("rtree.insert-directory", "Insertion strategy for directory nodes."); /** * Insertion strategy for leaf nodes. */ - public static final OptionID LEAF_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.insert-leaf", "Insertion strategy for leaf nodes."); + public static final OptionID LEAF_STRATEGY_ID = new OptionID("rtree.insert-leaf", "Insertion strategy for leaf nodes."); /** * Strategy when inserting into directory nodes diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java index 2532f351..3c25cbbc 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java @@ -111,7 +111,7 @@ public class LimitedReinsertOverflowTreatment implements OverflowTreatment { /** * Fast-insertion parameter. Optional. */ - public static OptionID REINSERT_STRATEGY_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-strategy", "The strategy to select candidates for reinsertion."); + public static OptionID REINSERT_STRATEGY_ID = new OptionID("rtree.reinsertion-strategy", "The strategy to select candidates for reinsertion."); /** * The actual reinsertion strategy diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java index e0277606..bb222dfe 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java @@ -27,7 +27,8 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDista import de.lmu.ifi.dbs.elki.distance.distancefunction.SquaredEuclideanDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -68,16 +69,16 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { * * @apiviz.exclude */ - public static abstract class Parameterizer extends AbstractParameterizer { + public abstract static class Parameterizer extends AbstractParameterizer { /** * Reinsertion share */ - public static OptionID REINSERT_AMOUNT_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-amount", "The amount of entries to reinsert."); + public static OptionID REINSERT_AMOUNT_ID = new OptionID("rtree.reinsertion-amount", "The amount of entries to reinsert."); /** * Reinsertion share */ - public static OptionID REINSERT_DISTANCE_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-distancce", "The distance function to compute reinsertion candidates by."); + public static OptionID REINSERT_DISTANCE_ID = new OptionID("rtree.reinsertion-distancce", "The distance function to compute reinsertion candidates by."); /** * The actual reinsertion strategy @@ -92,12 +93,14 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - DoubleParameter reinsertAmountP = new DoubleParameter(REINSERT_AMOUNT_ID, new IntervalConstraint(0.0, IntervalConstraint.IntervalBoundary.OPEN, 0.5, IntervalConstraint.IntervalBoundary.OPEN), 0.3); - if(config.grab(reinsertAmountP)) { + DoubleParameter reinsertAmountP = new DoubleParameter(REINSERT_AMOUNT_ID, 0.3); + reinsertAmountP.addConstraint(new GreaterConstraint(0.0)); + reinsertAmountP.addConstraint(new LessConstraint(0.5)); + if (config.grab(reinsertAmountP)) { reinsertAmount = reinsertAmountP.getValue(); } ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); - if(config.grab(distanceP)) { + if (config.grab(distanceP)) { distanceFunction = distanceP.instantiateClass(config); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java index e59fe10e..3e3d599c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java @@ -56,7 +56,7 @@ public class AngTanLinearSplit implements SplitStrategy { /** * Logger class */ - private static final Logging logger = Logging.getLogger(AngTanLinearSplit.class); + private static final Logging LOG = Logging.getLogger(AngTanLinearSplit.class); /** * Static instance. @@ -82,11 +82,11 @@ public class AngTanLinearSplit implements SplitStrategy { } for(int i = 0; i < num; i++) { E e = getter.get(entries, i); - for(int d = 1; d <= dim; d++) { + for(int d = 0; d < dim; d++) { double low = e.getMin(d) - total.getMin(d); double hig = total.getMax(d) - e.getMax(d); if(low >= hig) { - closer[d - 1].set(i); + closer[d].set(i); } } } @@ -105,7 +105,7 @@ public class AngTanLinearSplit implements SplitStrategy { continue; } if(card < bestcard) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = Double.NaN; @@ -117,16 +117,16 @@ public class AngTanLinearSplit implements SplitStrategy { } double overlap = computeOverlap(entries, getter, cand); if(overlap < bestover) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = overlap; } else if(overlap == bestover) { double bestlen = total.getMax(axis) - total.getMin(axis); - double candlen = total.getMax(d + 1) - total.getMin(d + 1); + double candlen = total.getMax(d) - total.getMin(d); if(candlen < bestlen) { - axis = d + 1; + axis = d; bestcard = card; bestset = cand; bestover = overlap; @@ -135,8 +135,8 @@ public class AngTanLinearSplit implements SplitStrategy { } } if(bestset == null) { - logger.warning("No Ang-Tan-Split found. Probably all points are the same? Returning random split."); - return Util.randomBitSet(num / 2, num, new Random()); + LOG.warning("No Ang-Tan-Split found. Probably all points are the same? Returning random split."); + return Util.randomBitSet(num >> 1, num, new Random()); } return bestset; } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java index 7401fbe5..99c15fd6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java @@ -70,72 +70,83 @@ public class GreeneSplit implements SplitStrategy { // Compute individual areas double[] areas = new double[num]; - for(int e1 = 0; e1 < num - 1; e1++) { + for (int e1 = 0; e1 < num - 1; e1++) { final E e1i = getter.get(entries, e1); areas[e1] = SpatialUtil.volume(e1i); } // Compute area increase - for(int e1 = 0; e1 < num - 1; e1++) { + for (int e1 = 0; e1 < num - 1; e1++) { final E e1i = getter.get(entries, e1); - for(int e2 = e1 + 1; e2 < num; e2++) { + for (int e2 = e1 + 1; e2 < num; e2++) { final E e2i = getter.get(entries, e2); final double areaJ = SpatialUtil.volumeUnion(e1i, e2i); final double d = areaJ - areas[e1] - areas[e2]; - if(d > worst) { + if (d > worst) { worst = d; w1 = e1; w2 = e2; } } } - // Data to keep - // Initial mbrs and areas - E m1 = getter.get(entries, w1); - E m2 = getter.get(entries, w2); + if (worst > 0) { + // Data to keep + // Initial mbrs and areas + E m1 = getter.get(entries, w1); + E m2 = getter.get(entries, w2); - double bestsep = Double.NEGATIVE_INFINITY; - double bestsep2 = Double.NEGATIVE_INFINITY; - for(int d = 1; d <= m1.getDimensionality(); d++) { - final double s1 = m1.getMin(d) - m2.getMax(d); - final double s2 = m2.getMin(d) - m1.getMax(d); - final double sm = Math.max(s1, s2); - final double no = Math.max(m1.getMax(d), m2.getMax(d)) - Math.min(m1.getMin(d), m2.getMin(d)); - final double sep = sm / no; - if(sep > bestsep || (sep == bestsep && sm > bestsep2)) { - bestsep = sep; - bestsep2 = sm; - axis = d; + double bestsep = Double.NEGATIVE_INFINITY; + double bestsep2 = Double.NEGATIVE_INFINITY; + for (int d = 0; d < m1.getDimensionality(); d++) { + final double s1 = m1.getMin(d) - m2.getMax(d); + final double s2 = m2.getMin(d) - m1.getMax(d); + final double sm = Math.max(s1, s2); + final double no = Math.max(m1.getMax(d), m2.getMax(d)) - Math.min(m1.getMin(d), m2.getMin(d)); + final double sep = sm / no; + if (sep > bestsep || (sep == bestsep && sm > bestsep2)) { + bestsep = sep; + bestsep2 = sm; + axis = d; + } + } + } else { + // All objects are identical! + final BitSet assignment = new BitSet(num); + final int half = (num + 1) >> 1; + // Put the first half into second node + for (int i = 0; i < half; i++) { + assignment.set(i); } + return assignment; } } // Sort by minimum value DoubleIntPair[] data = new DoubleIntPair[num]; - for(int i = 0; i < num; i++) { + for (int i = 0; i < num; i++) { data[i] = new DoubleIntPair(getter.get(entries, i).getMin(axis), i); } Arrays.sort(data); // Object assignment final BitSet assignment = new BitSet(num); - final int half = (num + 1) / 2; + final int half = (num + 1) >> 1; // Put the first half into second node - for(int i = 0; i < half; i++) { + for (int i = 0; i < half; i++) { assignment.set(data[i].second); } // Tie handling - if(num % 2 == 0) { + if (num % 2 == 0) { // We need to compute the bounding boxes ModifiableHyperBoundingBox mbr1 = new ModifiableHyperBoundingBox(getter.get(entries, data[0].second)); - for(int i = 1; i < half; i++) { + for (int i = 1; i < half; i++) { mbr1.extend(getter.get(entries, data[i].second)); } ModifiableHyperBoundingBox mbr2 = new ModifiableHyperBoundingBox(getter.get(entries, data[num - 1].second)); - for(int i = half + 1; i < num - 1; i++) { + for (int i = half + 1; i < num - 1; i++) { mbr2.extend(getter.get(entries, data[i].second)); } E e = getter.get(entries, data[half].second); double inc1 = SpatialUtil.volumeUnion(mbr1, e) - SpatialUtil.volume(mbr1); double inc2 = SpatialUtil.volumeUnion(mbr2, e) - SpatialUtil.volume(mbr2); - if(inc1 < inc2) { + if (inc1 < inc2) { assignment.set(data[half].second); } } @@ -155,4 +166,4 @@ public class GreeneSplit implements SplitStrategy { return GreeneSplit.STATIC; } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java index 296f6b3b..b4ff2364 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java @@ -67,7 +67,7 @@ public class RTreeLinearSplit implements SplitStrategy { double bestsep = Double.NEGATIVE_INFINITY; int w1 = -1, w2 = -1; // LPS1: find extreme rectangles - for(int d = 1; d <= dim; d++) { + for(int d = 0; d < dim; d++) { // We need to find two candidates each, in case of el==eh! double minlow = Double.POSITIVE_INFINITY; double maxlow = Double.NEGATIVE_INFINITY, maxlow2 = Double.NEGATIVE_INFINITY; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java index 1789ab22..ab32ba19 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java @@ -105,22 +105,25 @@ public class TopologicalSplitter implements SplitStrategy { private A entries; /** - * The getter class for the entries + * The getter class for the entries. */ private ArrayAdapter<E, A> getter; /** - * List size + * List size. */ private int size; /** - * Dimensionality + * Dimensionality. */ private int dimensionality; /** * Constructor. + * + * @param entries Entires to split + * @param getter Array adapter for entries */ public Split(A entries, ArrayAdapter<E, A> getter) { this.entries = entries; @@ -140,7 +143,7 @@ public class TopologicalSplitter implements SplitStrategy { double minSurface = Double.MAX_VALUE; int splitAxis = -1; - for(int d = 1; d <= dimensionality; d++) { + for(int d = 0; d < dimensionality; d++) { double sumOfAllMargins = 0; fillAndSort(d); @@ -180,7 +183,7 @@ public class TopologicalSplitter implements SplitStrategy { } /** - * Init the arrays we use + * Init the arrays we use. */ protected void initMinMaxArrays() { maxSorting = new DoubleIntPair[size]; @@ -227,7 +230,7 @@ public class TopologicalSplitter implements SplitStrategy { // is best for the split axis bestSorting = null; - assert (size - 2 * minEntries > 0) : "Cannot split underfull nodes."; + assert (size - 2 * minEntries >= 0) : "Cannot split nodes (" + size + " < 2*" + minEntries + ")"; // test the sorting with respect to the minimal values { ModifiableHyperBoundingBox mbr1 = mbr(minSorting, 0, minEntries - 1); @@ -267,10 +270,22 @@ public class TopologicalSplitter implements SplitStrategy { assert (splitPoint < size) : "No split found? Volume outside of double precision?"; } + /** + * Get an entry. + * + * @param off Offset + * @return Entry + */ private E get(int off) { return getter.get(entries, off); } + /** + * Get an entry. + * + * @param pair Entry pair + * @return Entry + */ private E get(DoubleIntPair pair) { return getter.get(entries, pair.second); } @@ -306,4 +321,4 @@ public class TopologicalSplitter implements SplitStrategy { return TopologicalSplitter.STATIC; } } -}
\ No newline at end of file +} |