diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/metrical/mtreevariants/mktrees')
16 files changed, 352 insertions, 369 deletions
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") |