diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants')
28 files changed, 903 insertions, 785 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/AbstractMTree.java index 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); } |