diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial')
86 files changed, 2548 insertions, 644 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialDirectoryEntry.java index 4a131cbf..ee7adf51 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialEntry.java index 4fe55adf..94c7bf33 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialIndexTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialIndexTree.java index b4bd5208..ad3ae29c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialIndexTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialIndexTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialNode.java index 449992a2..27913d36 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPair.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPair.java index f69b1dd1..bc0c6c94 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPair.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java index d79893b0..61dbf7d7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/SpatialPointLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -39,7 +39,7 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; * * @author Elke Achtert */ -public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialEntry, NumberVector<Double> { +public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialEntry, NumberVector { /** * Serial version. */ @@ -74,7 +74,7 @@ public class SpatialPointLeafEntry extends AbstractLeafEntry implements SpatialE * @param id Object id * @param vector Number vector */ - public SpatialPointLeafEntry(DBID id, NumberVector<?> vector) { + public SpatialPointLeafEntry(DBID id, NumberVector vector) { super(id); int dim = vector.getDimensionality(); this.values = new double[dim]; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/MinimalisticMemoryKDTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/MinimalisticMemoryKDTree.java index ce1da63c..c55a454d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/MinimalisticMemoryKDTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/MinimalisticMemoryKDTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.kd; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -31,10 +31,10 @@ import de.lmu.ifi.dbs.elki.data.type.TypeUtil; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPairList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDoubleDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; 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.KNNQuery; @@ -43,12 +43,10 @@ import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancefunction.DoubleNorm; +import de.lmu.ifi.dbs.elki.distance.distancefunction.Norm; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.LPNormDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SparseLPNormDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; -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.AbstractIndex; import de.lmu.ifi.dbs.elki.index.IndexFactory; import de.lmu.ifi.dbs.elki.index.KNNIndex; @@ -73,7 +71,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @param <O> Vector type */ @Reference(authors = "J. L. Bentley", title = "Multidimensional binary search trees used for associative searching", booktitle = "Communications of the ACM, Vol. 18 Issue 9, Sept. 1975", url = "http://dx.doi.org/10.1145/361002.361007") -public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends AbstractIndex<O> implements KNNIndex<O>, RangeIndex<O> { +public class MinimalisticMemoryKDTree<O extends NumberVector> extends AbstractIndex<O> implements KNNIndex<O>, RangeIndex<O> { /** * Class logger */ @@ -187,36 +185,34 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac } } - @SuppressWarnings("unchecked") @Override - public <D extends Distance<D>> KNNQuery<O, D> getKNNQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> df = distanceQuery.getDistanceFunction(); // TODO: if we know this works for other distance functions, add them, too! if(df instanceof LPNormDistanceFunction) { - return (KNNQuery<O, D>) new KDTreeKNNQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeKNNQuery(distanceQuery, (Norm<? super O>) df); } if(df instanceof SquaredEuclideanDistanceFunction) { - return (KNNQuery<O, D>) new KDTreeKNNQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeKNNQuery(distanceQuery, (Norm<? super O>) df); } if(df instanceof SparseLPNormDistanceFunction) { - return (KNNQuery<O, D>) new KDTreeKNNQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeKNNQuery(distanceQuery, (Norm<? super O>) df); } return null; } - @SuppressWarnings("unchecked") @Override - public <D extends Distance<D>> RangeQuery<O, D> getRangeQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { - DistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { + DistanceFunction<? super O> df = distanceQuery.getDistanceFunction(); // TODO: if we know this works for other distance functions, add them, too! if(df instanceof LPNormDistanceFunction) { - return (RangeQuery<O, D>) new KDTreeRangeQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeRangeQuery(distanceQuery, (Norm<? super O>) df); } if(df instanceof SquaredEuclideanDistanceFunction) { - return (RangeQuery<O, D>) new KDTreeRangeQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeRangeQuery(distanceQuery, (Norm<? super O>) df); } if(df instanceof SparseLPNormDistanceFunction) { - return (RangeQuery<O, D>) new KDTreeRangeQuery((DistanceQuery<O, DoubleDistance>) distanceQuery, (DoubleNorm<? super O>) df); + return new KDTreeRangeQuery(distanceQuery, (Norm<? super O>) df); } return null; } @@ -226,11 +222,11 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * * @author Erich Schubert */ - public class KDTreeKNNQuery extends AbstractDistanceKNNQuery<O, DoubleDistance> { + public class KDTreeKNNQuery extends AbstractDistanceKNNQuery<O> { /** * Norm to use. */ - private DoubleNorm<? super O> norm; + private Norm<? super O> norm; /** * Constructor. @@ -238,14 +234,14 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * @param distanceQuery Distance query * @param norm Norm to use */ - public KDTreeKNNQuery(DistanceQuery<O, DoubleDistance> distanceQuery, DoubleNorm<? super O> norm) { + public KDTreeKNNQuery(DistanceQuery<O> distanceQuery, Norm<? super O> norm) { super(distanceQuery); this.norm = norm; } @Override - public KNNList<DoubleDistance> getKNNForObject(O obj, int k) { - final DoubleDistanceKNNHeap knns = DBIDUtil.newDoubleDistanceHeap(k); + public KNNList getKNNForObject(O obj, int k) { + final KNNHeap knns = DBIDUtil.newHeap(k); kdKNNSearch(0, sorted.size(), 0, obj, knns, sorted.iter(), Double.POSITIVE_INFINITY); return knns.toKNNList(); } @@ -262,7 +258,7 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * @param maxdist Current upper bound of kNN distance. * @return New upper bound of kNN distance. */ - private double kdKNNSearch(int left, int right, int axis, O query, DoubleDistanceKNNHeap knns, DBIDArrayIter iter, double maxdist) { + private double kdKNNSearch(int left, int right, int axis, O query, KNNHeap knns, DBIDArrayIter iter, double maxdist) { // Look at current node: final int middle = (left + right) >>> 1; iter.seek(middle); @@ -280,12 +276,12 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac // Exact match chance (delta == 0)! // process first, then descend both sides. if(onleft && onright) { - double dist = norm.doubleDistance(query, split); + double dist = norm.distance(query, split); countDistanceComputation(); if(dist <= maxdist) { iter.seek(middle); knns.insert(dist, iter); - maxdist = knns.doubleKNNDistance(); + maxdist = knns.getKNNDistance(); } if(left < middle) { maxdist = kdKNNSearch(left, middle, next, query, knns, iter, maxdist); @@ -301,12 +297,12 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac } // Look at splitting element (unless already above): if(Math.abs(delta) <= maxdist) { - double dist = norm.doubleDistance(query, split); + double dist = norm.distance(query, split); countDistanceComputation(); if(dist <= maxdist) { iter.seek(middle); knns.insert(dist, iter); - maxdist = knns.doubleKNNDistance(); + maxdist = knns.getKNNDistance(); } } if((middle + 1 < right) && (Math.abs(delta) <= maxdist)) { @@ -319,12 +315,12 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac } // Look at splitting element (unless already above): if(Math.abs(delta) <= maxdist) { - double dist = norm.doubleDistance(query, split); + double dist = norm.distance(query, split); countDistanceComputation(); if(dist <= maxdist) { iter.seek(middle); knns.insert(dist, iter); - maxdist = knns.doubleKNNDistance(); + maxdist = knns.getKNNDistance(); } } if((left < middle) && (Math.abs(delta) <= maxdist)) { @@ -341,11 +337,11 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * * @author Erich Schubert */ - public class KDTreeRangeQuery extends AbstractDistanceRangeQuery<O, DoubleDistance> { + public class KDTreeRangeQuery extends AbstractDistanceRangeQuery<O> { /** * Norm to use. */ - private DoubleNorm<? super O> norm; + private Norm<? super O> norm; /** * Constructor. @@ -353,15 +349,15 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * @param distanceQuery Distance query * @param norm Norm to use */ - public KDTreeRangeQuery(DistanceQuery<O, DoubleDistance> distanceQuery, DoubleNorm<? super O> norm) { + public KDTreeRangeQuery(DistanceQuery<O> distanceQuery, Norm<? super O> norm) { super(distanceQuery); this.norm = norm; } @Override - public DoubleDistanceDBIDPairList getRangeForObject(O obj, DoubleDistance range) { - final DoubleDistanceDBIDPairList res = new DoubleDistanceDBIDPairList(); - kdRangeSearch(0, sorted.size(), 0, obj, res, sorted.iter(), range.doubleValue()); + public DoubleDBIDList getRangeForObject(O obj, double range) { + final ModifiableDoubleDBIDList res = DBIDUtil.newDistanceDBIDList(); + kdRangeSearch(0, sorted.size(), 0, obj, res, sorted.iter(), range); res.sort(); return res; } @@ -377,7 +373,7 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * @param iter Iterator variable (reduces memory footprint!) * @param radius Query radius */ - private void kdRangeSearch(int left, int right, int axis, O query, ModifiableDoubleDistanceDBIDList res, DBIDArrayIter iter, double radius) { + private void kdRangeSearch(int left, int right, int axis, O query, ModifiableDoubleDBIDList res, DBIDArrayIter iter, double radius) { // Look at current node: final int middle = (left + right) >>> 1; iter.seek(middle); @@ -395,7 +391,7 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac // Current object: if(close) { - double dist = norm.doubleDistance(query, split); + double dist = norm.distance(query, split); countDistanceComputation(); if(dist <= radius) { iter.seek(middle); @@ -421,8 +417,8 @@ public class MinimalisticMemoryKDTree<O extends NumberVector<?>> extends Abstrac * * @param <O> Vector type */ - @Alias({"minikd", "kd"}) - public static class Factory<O extends NumberVector<?>> implements IndexFactory<O, MinimalisticMemoryKDTree<O>> { + @Alias({ "minikd", "kd" }) + public static class Factory<O extends NumberVector> implements IndexFactory<O, MinimalisticMemoryKDTree<O>> { /** * Constructor. Trivial parameterizable. */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/package-info.java index 88a42c2d..eab62562 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/kd/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/package-info.java index 7fbdd2ac..d69e1516 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/package-info.java @@ -1,11 +1,13 @@ /** * <p>Tree-based index structures for <em>spatial</em> indexing.</p> + * + * @apiviz.exclude de.lmu.ifi.dbs.elki.tree.spatial.rstarvariants.deliclu */ /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java index 63c8e8fa..8b0e5998 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java index 70e9f747..b51bfe10 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -56,7 +56,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * @param <E> Entry type * @param <I> Index type */ -public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E, S> & Index, S extends AbstractRTreeSettings> extends PagedIndexFactory<O, I> { +public abstract class AbstractRStarTreeFactory<O extends NumberVector, N extends AbstractRStarTreeNode<N, E>, E extends SpatialEntry, I extends AbstractRStarTree<N, E, S> & Index, S extends AbstractRTreeSettings> extends PagedIndexFactory<O, I> { /** * Tree settings */ @@ -88,7 +88,7 @@ public abstract class AbstractRStarTreeFactory<O extends NumberVector<?>, N exte * @param <O> Object type * @param <S> Settings class */ - public abstract static class Parameterizer<O extends NumberVector<?>, S extends AbstractRTreeSettings> extends PagedIndexFactory.Parameterizer<O> { + public abstract static class Parameterizer<O extends NumberVector, S extends AbstractRTreeSettings> extends PagedIndexFactory.Parameterizer<O> { /** * Fast-insertion parameter. Optional. */ diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java index 6b5fc2f0..18f22ceb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRStarTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java index f876be13..40a2aa6c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/AbstractRTreeSettings.java @@ -12,7 +12,7 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.Top This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java index 8a4f530f..eb04eec7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/NonFlatRStarTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java index 510120c9..eab4a7d6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluDirectoryEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java index f72b7d8d..8478c0b5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java index 741ab840..a2c8490b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluLeafEntry.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -62,7 +62,7 @@ public class DeLiCluLeafEntry extends SpatialPointLeafEntry implements DeLiCluEn * @param id the unique id of the underlying data object * @param vector the vector to store */ - public DeLiCluLeafEntry(DBID id, NumberVector<?> vector) { + public DeLiCluLeafEntry(DBID id, NumberVector vector) { super(id, vector); this.hasHandled = false; this.hasUnhandled = true; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java index 7b3221c3..4fc22177 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -61,7 +61,7 @@ public class DeLiCluNode extends AbstractRStarTreeNode<DeLiCluNode, DeLiCluEntry * handled data objects */ public boolean hasHandled() { - for(int i = 1; i < getNumEntries(); i++) { + for(int i = 0; i < getNumEntries(); i++) { boolean handled = getEntry(i).hasHandled(); if(handled) { return true; @@ -78,7 +78,7 @@ public class DeLiCluNode extends AbstractRStarTreeNode<DeLiCluNode, DeLiCluEntry * unhandled data objects */ public boolean hasUnhandled() { - for(int i = 1; i < getNumEntries(); i++) { + for(int i = 0; i < getNumEntries(); i++) { boolean handled = getEntry(i).hasUnhandled(); if(handled) { return true; diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java index 33366763..a2adca7f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java index a63b8004..b7770e79 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -40,7 +40,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; * * @param <O> Object type */ -public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>, AbstractRTreeSettings> { +public class DeLiCluTreeFactory<O extends NumberVector> extends AbstractRStarTreeFactory<O, DeLiCluNode, DeLiCluEntry, DeLiCluTreeIndex<O>, AbstractRTreeSettings> { /** * Constructor. * @@ -69,7 +69,7 @@ public class DeLiCluTreeFactory<O extends NumberVector<?>> extends AbstractRStar * * @apiviz.exclude */ - public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { + public static class Parameterizer<O extends NumberVector> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { @Override protected DeLiCluTreeFactory<O> makeInstance() { return new DeLiCluTreeFactory<>(pageFileFactory, settings); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java index 67c9c9e0..6bc6c171 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/DeLiCluTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -37,7 +37,6 @@ import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -56,7 +55,7 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @param <O> Object type */ -public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O>, DynamicIndex { +public class DeLiCluTreeIndex<O extends NumberVector> extends DeLiCluTree implements KNNIndex<O>, RangeIndex<O>, DynamicIndex { /** * The relation we index. */ @@ -97,14 +96,14 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp * @return the path of node ids from the root to the objects's parent */ public synchronized List<TreeIndexPathComponent<DeLiCluEntry>> setHandled(DBID id, O obj) { - if (LOG.isDebugging()) { + if(LOG.isDebugging()) { LOG.debugFine("setHandled " + id + ", " + obj + "\n"); } // find the leaf node containing o IndexTreePath<DeLiCluEntry> pathToObject = findPathToObject(getRootPath(), obj, id); - if (pathToObject == null) { + if(pathToObject == null) { throw new AbortException("Object not found in setHandled."); } @@ -113,12 +112,12 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp entry.setHasHandled(true); entry.setHasUnhandled(false); - for (IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { + for(IndexTreePath<DeLiCluEntry> path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) { DeLiCluEntry parentEntry = path.getParentPath().getLastPathComponent().getEntry(); DeLiCluNode node = getNode(parentEntry); boolean hasHandled = false; boolean hasUnhandled = false; - for (int i = 0; i < node.getNumEntries(); i++) { + for(int i = 0; i < node.getNumEntries(); i++) { final DeLiCluEntry nodeEntry = node.getEntry(i); hasHandled = hasHandled || nodeEntry.hasHandled(); hasUnhandled = hasUnhandled || nodeEntry.hasUnhandled(); @@ -154,19 +153,20 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp */ @Override public final void insertAll(DBIDs ids) { - if (ids.isEmpty() || (ids.size() == 1)) { + if(ids.isEmpty() || (ids.size() == 1)) { return; } // Make an example leaf - if (canBulkLoad()) { + if(canBulkLoad()) { List<DeLiCluEntry> leafs = new ArrayList<>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); } bulkLoad(leafs); - } else { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + } + else { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { insert(iter); } } @@ -185,7 +185,7 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp // find the leaf node containing o O obj = relation.get(id); IndexTreePath<DeLiCluEntry> deletionPath = findPathToObject(getRootPath(), obj, id); - if (deletionPath == null) { + if(deletionPath == null) { return false; } deletePath(deletionPath); @@ -194,36 +194,36 @@ public class DeLiCluTreeIndex<O extends NumberVector<?>> extends DeLiCluTree imp @Override public void deleteAll(DBIDs ids) { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { delete(DBIDUtil.deref(iter)); } } @Override - public <D extends Distance<D>> RangeQuery<O, D> getRangeQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index - if (distanceQuery.getRelation() != relation) { + if(distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if (!(distanceQuery instanceof SpatialDistanceQuery)) { + if(!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } - SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; return RStarTreeUtil.getRangeQuery(this, dq, hints); } @Override - public <D extends Distance<D>> KNNQuery<O, D> getKNNQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index - if (distanceQuery.getRelation() != relation) { + if(distanceQuery.getRelation() != relation) { return null; } // Can we support this distance function - spatial distances only! - if (!(distanceQuery instanceof SpatialDistanceQuery)) { + if(!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } - SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; return RStarTreeUtil.getKNNQuery(this, dq, hints); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java index f8bec8cb..e17df1ca 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/deliclu/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTree.java new file mode 100644 index 00000000..498abc58 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTree.java @@ -0,0 +1,228 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.data.ModifiableHyperBoundingBox; +import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.persistent.PageFile; + +/** + * FlatRTree is a spatial index structure based on a R*-Tree but with a flat + * directory. Apart from organizing the objects it also provides several methods + * to search for certain object in the structure and ensures persistence. + * + * @author Elke Achtert + * + * @apiviz.has FlatRStarTreeNode oneway - - contains + */ +public class FlatRStarTree extends AbstractRStarTree<FlatRStarTreeNode, SpatialEntry, AbstractRTreeSettings> { + /** + * The logger for this class. + */ + private static final Logging LOG = Logging.getLogger(FlatRStarTree.class); + + /** + * The root of this flat RTree. + */ + private FlatRStarTreeNode root; + + /** + * Constructor. + * + * @param pagefile Page file + * @param settings Tree settings + */ + public FlatRStarTree(PageFile<FlatRStarTreeNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); + } + + /** + * Initializes the flat RTree from an existing persistent file. + */ + @Override + public void initializeFromFile(TreeIndexHeader header, PageFile<FlatRStarTreeNode> file) { + super.initializeFromFile(header, file); + + // reconstruct root + int nextPageID = file.getNextPageID(); + dirCapacity = nextPageID; + root = createNewDirectoryNode(); + for(int i = 1; i < nextPageID; i++) { + FlatRStarTreeNode node = getNode(i); + root.addDirectoryEntry(createNewDirectoryEntry(node)); + } + + if(LOG.isDebugging()) { + LOG.debugFine("root: " + root + " with " + nextPageID + " leafNodes."); + } + } + + /** + * Returns the root node of this RTree. + * + * @return the root node of this RTree + */ + @Override + public FlatRStarTreeNode getRoot() { + return root; + } + + /** + * Returns the height of this FlatRTree. + * + * @return 2 + */ + @Override + protected int computeHeight() { + return 2; + } + + /** + * Performs a bulk load on this RTree with the specified data. Is called by + * the constructor and should be overwritten by subclasses if necessary. + */ + @Override + protected void bulkLoad(List<SpatialEntry> spatialObjects) { + if(!initialized) { + initialize(spatialObjects.get(0)); + } + // create leaf nodes + getFile().setNextPageID(getRootID() + 1); + List<SpatialEntry> nodes = createBulkLeafNodes(spatialObjects); + int numNodes = nodes.size(); + if(LOG.isDebugging()) { + LOG.debugFine(" numLeafNodes = " + numNodes); + } + + // create root + root = createNewDirectoryNode(); + root.setPageID(getRootID()); + for(SpatialEntry entry : nodes) { + root.addDirectoryEntry(entry); + } + numNodes++; + setHeight(2); + + if(LOG.isDebugging()) { + StringBuilder msg = new StringBuilder(); + msg.append(" root = ").append(getRoot()); + msg.append("\n numNodes = ").append(numNodes); + msg.append("\n height = ").append(getHeight()); + LOG.debugFine(msg.toString() + "\n"); + } + doExtraIntegrityChecks(); + } + + @Override + protected void createEmptyRoot(SpatialEntry exampleLeaf) { + root = createNewDirectoryNode(); + root.setPageID(getRootID()); + + getFile().setNextPageID(getRootID() + 1); + FlatRStarTreeNode leaf = createNewLeafNode(); + writeNode(leaf); + ModifiableHyperBoundingBox mbr = new ModifiableHyperBoundingBox(new double[exampleLeaf.getDimensionality()], new double[exampleLeaf.getDimensionality()]); + root.addDirectoryEntry(new SpatialDirectoryEntry(leaf.getPageID(), mbr)); + + setHeight(2); + } + + /** + * Returns true if in the specified node an overflow occurred, false + * otherwise. + * + * @param node the node to be tested for overflow + * @return true if in the specified node an overflow occurred, false otherwise + */ + @Override + protected boolean hasOverflow(FlatRStarTreeNode node) { + if(node.isLeaf()) { + return node.getNumEntries() == leafCapacity; + } + else if(node.getNumEntries() == node.getCapacity()) { + node.increaseEntries(); + } + return false; + } + + /** + * Returns true if in the specified node an underflow occurred, false + * otherwise. + * + * @param node the node to be tested for underflow + * @return true if in the specified node an underflow occurred, false + * otherwise + */ + @Override + protected boolean hasUnderflow(FlatRStarTreeNode node) { + if(node.isLeaf()) { + return node.getNumEntries() < leafMinimum; + } + else { + return false; + } + } + + /** + * Creates a new leaf node with the specified capacity. + * + * @return a new leaf node + */ + @Override + protected FlatRStarTreeNode createNewLeafNode() { + return new FlatRStarTreeNode(leafCapacity, true); + } + + /** + * Creates a new directory node with the specified capacity. + * + * @return a new directory node + */ + @Override + protected FlatRStarTreeNode createNewDirectoryNode() { + return new FlatRStarTreeNode(dirCapacity, false); + } + + @Override + protected SpatialEntry createNewDirectoryEntry(FlatRStarTreeNode node) { + return new SpatialDirectoryEntry(node.getPageID(), node.computeMBR()); + } + + @Override + protected SpatialEntry createRootEntry() { + return new SpatialDirectoryEntry(0, null); + } + + @Override + protected Logging getLogger() { + return LOG; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeFactory.java new file mode 100644 index 00000000..ea631ecd --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeFactory.java @@ -0,0 +1,84 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeFactory; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; +import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; + +/** + * Factory for flat R*-Trees. + * + * @author Erich Schubert + * + * @apiviz.stereotype factory + * @apiviz.uses FlatRStarTreeIndex oneway - - «create» + * + * @param <O> Object type + */ +public class FlatRStarTreeFactory<O extends NumberVector> extends AbstractRStarTreeFactory<O, FlatRStarTreeNode, SpatialEntry, FlatRStarTreeIndex<O>, AbstractRTreeSettings> { + /** + * Constructor. + * + * @param pageFileFactory Data storage + * @param settings Index settings + */ + public FlatRStarTreeFactory(PageFileFactory<?> pageFileFactory, AbstractRTreeSettings settings) { + super(pageFileFactory, settings); + } + + @Override + public FlatRStarTreeIndex<O> instantiate(Relation<O> relation) { + PageFile<FlatRStarTreeNode> pagefile = makePageFile(getNodeClass()); + FlatRStarTreeIndex<O> index = new FlatRStarTreeIndex<>(relation, pagefile, settings); + return index; + } + + protected Class<FlatRStarTreeNode> getNodeClass() { + return FlatRStarTreeNode.class; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer<O extends NumberVector> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { + @Override + protected FlatRStarTreeFactory<O> makeInstance() { + return new FlatRStarTreeFactory<>(pageFileFactory, settings); + } + + @Override + protected AbstractRTreeSettings createSettings() { + return new AbstractRTreeSettings(); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java new file mode 100644 index 00000000..6b5204e5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java @@ -0,0 +1,203 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.ArrayList; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.index.DynamicIndex; +import de.lmu.ifi.dbs.elki.index.KNNIndex; +import de.lmu.ifi.dbs.elki.index.RangeIndex; +import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.persistent.PageFile; + +/** + * The common use of the flat rstar tree: indexing number vectors. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public class FlatRStarTreeIndex<O extends NumberVector> extends FlatRStarTree implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { + /** + * The relation we index + */ + private Relation<O> relation; + + /** + * Constructor. + * + * @param relation Relation to index + * @param pagefile Page file + * @param settings Tree settings + */ + public FlatRStarTreeIndex(Relation<O> relation, PageFile<FlatRStarTreeNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); + this.relation = relation; + } + + /** + * The appropriate logger for this index. + */ + private static final Logging LOG = Logging.getLogger(FlatRStarTreeIndex.class); + + /** + * Wrap a vector as spatial point leaf entry. + * + * @param id Object DBID + * @return spatial leaf + */ + protected SpatialEntry createNewLeafEntry(DBID id) { + return new SpatialPointLeafEntry(id, relation.get(id)); + } + + @Override + public void initialize() { + super.initialize(); + insertAll(relation.getDBIDs()); + } + + /** + * Inserts the specified real vector object into this index. + * + * @param id the object id that was inserted + */ + @Override + public final void insert(DBIDRef id) { + insertLeaf(createNewLeafEntry(DBIDUtil.deref(id))); + } + + /** + * Inserts the specified objects into this index. If a bulk load mode is + * implemented, the objects are inserted in one bulk. + * + * @param ids the objects to be inserted + */ + @Override + public final void insertAll(DBIDs ids) { + if(ids.isEmpty() || (ids.size() == 1)) { + return; + } + + // Make an example leaf + if(canBulkLoad()) { + List<SpatialEntry> leafs = new ArrayList<>(ids.size()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); + } + bulkLoad(leafs); + } + else { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + insert(iter); + } + } + + doExtraIntegrityChecks(); + } + + /** + * Deletes the specified object from this index. + * + * @return true if this index did contain the object with the specified id, + * false otherwise + */ + @Override + public final boolean delete(DBIDRef id) { + // find the leaf node containing o + O obj = relation.get(id); + IndexTreePath<SpatialEntry> deletionPath = findPathToObject(getRootPath(), obj, id); + if(deletionPath == null) { + return false; + } + deletePath(deletionPath); + return true; + } + + @Override + public void deleteAll(DBIDs ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + delete(DBIDUtil.deref(iter)); + } + } + + @Override + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // Query on the relation we index + if(distanceQuery.getRelation() != relation) { + return null; + } + // Can we support this distance function - spatial distances only! + if(!(distanceQuery instanceof SpatialDistanceQuery)) { + return null; + } + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; + return RStarTreeUtil.getRangeQuery(this, dq, hints); + } + + @Override + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // Query on the relation we index + if(distanceQuery.getRelation() != relation) { + return null; + } + // Can we support this distance function - spatial distances only! + if(!(distanceQuery instanceof SpatialDistanceQuery)) { + return null; + } + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; + return RStarTreeUtil.getKNNQuery(this, dq, hints); + } + + @Override + public String getLongName() { + return "Flat R*-Tree"; + } + + @Override + public String getShortName() { + return "flatrstartree"; + } + + @Override + protected Logging getLogger() { + return LOG; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeNode.java new file mode 100644 index 00000000..7015577d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeNode.java @@ -0,0 +1,81 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.index.tree.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; +import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; + +/** + * Represents a node in a flat R*-Tree. + * + * @author Elke Achtert + */ +public class FlatRStarTreeNode extends AbstractRStarTreeNode<FlatRStarTreeNode, SpatialEntry> { + /** + * Serial version + */ + private static final long serialVersionUID = 1; + + /** + * Empty constructor for Externalizable interface. + */ + public FlatRStarTreeNode() { + // empty constructor + } + + /** + * Deletes the entry at the specified index and shifts all entries after the + * index to left. + * + * @param index the index at which the entry is to be deleted + */ + @Override + public boolean deleteEntry(int index) { + if(this.getPageID() == 0 && index == 0 && getNumEntries() == 1) { + return false; + } + return super.deleteEntry(index); + } + + /** + * Creates a new FlatRStarTreeNode with the specified parameters. + * + * @param capacity the capacity (maximum number of entries plus 1 for + * overflow) of this node + * @param isLeaf indicates whether this node is a leaf node + */ + public FlatRStarTreeNode(int capacity, boolean isLeaf) { + super(capacity, isLeaf, SpatialEntry.class); + } + + /** + * Increases the length of the entries array to entries.length + 1. + */ + public final void increaseEntries() { + SpatialEntry[] tmp = entries; + entries = ClassGenericsUtil.newArrayOfNull(tmp.length + 1, SpatialEntry.class); + System.arraycopy(tmp, 0, entries, 0, tmp.length); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/package-info.java new file mode 100644 index 00000000..fd092666 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>{@link de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat.FlatRStarTree}</p> + */ +/* +This file is part of ELKI: +Environment for Developing KDD-Applications Supported by Index-Structures + +Copyright (C) 2014 +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/>. +*/ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat;
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java index e50cc513..aa47110c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeKNNQuery.java new file mode 100644 index 00000000..e1763d3e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeKNNQuery.java @@ -0,0 +1,167 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.QueryUtil; +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.query.DoubleDistanceSearchCandidate; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; + +/** + * Instance of a KNN query for a particular spatial index. + * + * Reference: + * <p> + * G. R. Hjaltason, H. Samet<br /> + * Ranking in spatial databases<br /> + * In: 4th Symposium on Advances in Spatial Databases, SSD'95 + * </p> + * + * @author Erich Schubert + * + * @apiviz.uses EuclideanDistanceFunction + * @apiviz.uses SquaredEuclideanDistanceFunction + */ +@Reference(authors = "G. R. Hjaltason, H. Samet", // +title = "Ranking in spatial databases", // +booktitle = "Advances in Spatial Databases - 4th Symposium, SSD'95", // +url = "http://dx.doi.org/10.1007/3-540-60159-7_6") +public class EuclideanRStarTreeKNNQuery<O extends NumberVector> extends RStarTreeKNNQuery<O> { + /** + * Squared euclidean distance function. + */ + private static final SquaredEuclideanDistanceFunction SQUARED = SquaredEuclideanDistanceFunction.STATIC; + + /** + * Constructor. + * + * @param tree Index to use + * @param relation Data relation to query + */ + public EuclideanRStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, Relation<? extends O> relation) { + super(tree, relation, EuclideanDistanceFunction.STATIC); + } + + @Override + public KNNList getKNNForObject(O obj, int k) { + if(k < 1) { + throw new IllegalArgumentException("At least one neighbor has to be requested!"); + } + tree.statistics.countKNNQuery(); + + final KNNHeap knnList = DBIDUtil.newHeap(k); + final ComparableMinHeap<DoubleDistanceSearchCandidate> pq = new ComparableMinHeap<>(Math.min(knnList.getK() << 1, 21)); + + // expand root + double maxDist = expandNode(obj, knnList, pq, Double.MAX_VALUE, tree.getRootID()); + + // search in tree + while(!pq.isEmpty()) { + DoubleDistanceSearchCandidate pqNode = pq.poll(); + + if(pqNode.mindist > maxDist) { + break; + } + maxDist = expandNode(obj, knnList, pq, maxDist, pqNode.nodeID); + } + return QueryUtil.applySqrt(knnList.toKNNList()); + } + + private double expandNode(O object, KNNHeap knnList, final ComparableMinHeap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { + AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); + // data node + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + SpatialPointLeafEntry entry = (SpatialPointLeafEntry) node.getEntry(i); + double distance = SQUARED.minDist(entry, object); + tree.statistics.countDistanceCalculation(); + if(distance <= maxDist) { + maxDist = knnList.insert(distance, entry.getDBID()); + } + } + } + // directory node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + SpatialDirectoryEntry entry = (SpatialDirectoryEntry) node.getEntry(i); + double distance = SQUARED.minDist(entry, object); + tree.statistics.countDistanceCalculation(); + // Greedy expand, bypassing the queue + if(distance <= 0) { + expandNode(object, knnList, pq, maxDist, entry.getPageID()); + } + else { + if(distance <= maxDist) { + pq.add(new DoubleDistanceSearchCandidate(distance, entry.getPageID())); + } + } + } + } + return maxDist; + } + + @Override + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + if(k < 1) { + throw new IllegalArgumentException("At least one enumeration has to be requested!"); + } + + // While this works, it seems to be slow at least for large sets! + // TODO: use a DataStore instead of a map. + final Map<DBID, KNNHeap> knnLists = new HashMap<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + knnLists.put(id, DBIDUtil.newHeap(k)); + } + + batchNN(tree.getRoot(), knnLists); + + List<KNNList> result = new ArrayList<>(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + tree.statistics.countKNNQuery(); + result.add(QueryUtil.applySqrt(knnLists.get(id).toKNNList())); + } + return result; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeRangeQuery.java new file mode 100644 index 00000000..0fcb633b --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/EuclideanRStarTreeRangeQuery.java @@ -0,0 +1,120 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.Arrays; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; + +/** + * Instance of a range query for a particular spatial index. + * + * Reference: + * <p> + * J. Kuan, P. Lewis<br /> + * Fast k nearest neighbour search for R-tree family<br /> + * In Proc. Int. Conf Information, Communications and Signal Processing, ICICS + * 1997 + * </p> + * + * @author Erich Schubert + * + * @apiviz.uses EuclideanDistanceFunction + * @apiviz.uses SquaredEuclideanDistanceFunction + */ +@Reference(authors = "J. Kuan, P. Lewis", title = "Fast k nearest neighbour search for R-tree family", booktitle = "Proc. Int. Conf Information, Communications and Signal Processing, ICICS 1997", url = "http://dx.doi.org/10.1109/ICICS.1997.652114") +public class EuclideanRStarTreeRangeQuery<O extends NumberVector> extends RStarTreeRangeQuery<O> { + /** + * Squared euclidean distance function. + */ + private static final SquaredEuclideanDistanceFunction SQUARED = SquaredEuclideanDistanceFunction.STATIC; + + /** + * Constructor. + * + * @param tree Index to use + * @param relation Relation to use. + */ + public EuclideanRStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, Relation<? extends O> relation) { + super(tree, relation, EuclideanDistanceFunction.STATIC); + } + + @Override + public DoubleDBIDList getRangeForObject(O object, double range) { + tree.statistics.countRangeQuery(); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + + final double sqepsilon = range * range; + + // Processing queue. + int[] pq = new int[101]; + int ps = 0; + pq[ps++] = tree.getRootID(); + + // search in tree + while(ps > 0) { + int pqNode = pq[--ps]; // Pop last. + AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode); + final int numEntries = node.getNumEntries(); + + if(node.isLeaf()) { + for(int i = 0; i < numEntries; i++) { + SpatialPointLeafEntry entry = (SpatialPointLeafEntry) node.getEntry(i); + double distance = SQUARED.minDist(object, entry); + tree.statistics.countDistanceCalculation(); + if(distance <= sqepsilon) { + result.add(Math.sqrt(distance), entry.getDBID()); + } + } + } + else { + for(int i = 0; i < numEntries; i++) { + SpatialDirectoryEntry entry = (SpatialDirectoryEntry) node.getEntry(i); + double distance = SQUARED.minDist(object, entry); + if(distance <= sqepsilon) { + if(ps == pq.length) { // Resize: + pq = Arrays.copyOf(pq, pq.length + (pq.length >>> 1)); + } + pq[ps++] = entry.getEntryID(); + } + } + } + } + + // sort the result according to the distances + result.sort(); + return result; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java deleted file mode 100644 index 229758ea..00000000 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeKNNQuery.java +++ /dev/null @@ -1,243 +0,0 @@ -package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2013 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; -import java.util.List; -import java.util.Map; -import java.util.Map.Entry; - -import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.distance.DistanceUtil; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; -import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; -import de.lmu.ifi.dbs.elki.index.tree.query.GenericDistanceSearchCandidate; -import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; -import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; -import de.lmu.ifi.dbs.elki.utilities.pairs.FCPair; - -/** - * Instance of a KNN query for a particular spatial index. - * - * Reference: - * <p> - * G. R. Hjaltason, H. Samet<br /> - * Ranking in spatial databases<br /> - * In: 4th Symposium on Advances in Spatial Databases, SSD'95 - * </p> - * - * @author Erich Schubert - * - * @apiviz.uses AbstractRStarTree - * @apiviz.uses SpatialPrimitiveDistanceFunction - */ -@Reference(authors = "G. R. Hjaltason, H. Samet", title = "Ranking in spatial databases", booktitle = "Advances in Spatial Databases - 4th Symposium, SSD'95", url = "http://dx.doi.org/10.1007/3-540-60159-7_6") -public class GenericRStarTreeKNNQuery<O extends SpatialComparable, D extends Distance<D>> extends AbstractDistanceKNNQuery<O, D> { - /** - * The index to use - */ - protected final AbstractRStarTree<?, ?, ?> tree; - - /** - * Spatial primitive distance function - */ - protected final SpatialPrimitiveDistanceFunction<? super O, D> distanceFunction; - - /** - * Constructor. - * - * @param tree Index to use - * @param distanceQuery Distance query to use - */ - public GenericRStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { - super(distanceQuery); - this.tree = tree; - this.distanceFunction = distanceQuery.getDistanceFunction(); - } - - /** - * Performs a batch knn query. - * - * @param node the node for which the query should be performed - * @param knnLists a map containing the knn lists for each query objects - */ - protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap<D>> knnLists) { - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - SpatialEntry p = node.getEntry(i); - for(Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { - final DBID q = ent.getKey(); - final KNNHeap<D> knns_q = ent.getValue(); - D knn_q_maxDist = knns_q.getKNNDistance(); - - DBID pid = ((LeafEntry) p).getDBID(); - // FIXME: objects are NOT accessible by DBID in a plain rtree context! - D dist_pq = distanceQuery.distance(pid, q); - tree.statistics.countDistanceCalculation(); - if(dist_pq.compareTo(knn_q_maxDist) <= 0) { - knns_q.insert(dist_pq, pid); - } - } - } - } - else { - ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size()); - for(DBID id : knnLists.keySet()) { - ids.add(id); - } - List<FCPair<D, SpatialEntry>> entries = getSortedEntries(node, ids); - for(FCPair<D, SpatialEntry> distEntry : entries) { - D minDist = distEntry.first; - for(Entry<DBID, KNNHeap<D>> ent : knnLists.entrySet()) { - final KNNHeap<D> knns_q = ent.getValue(); - D knn_q_maxDist = knns_q.getKNNDistance(); - - if(minDist.compareTo(knn_q_maxDist) <= 0) { - SpatialEntry entry = distEntry.second; - AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID().intValue()); - batchNN(child, knnLists); - break; - } - } - } - } - } - - /** - * Sorts the entries of the specified node according to their minimum distance - * to the specified objects. - * - * @param node the node - * @param ids the id of the objects - * @return a list of the sorted entries - */ - protected List<FCPair<D, SpatialEntry>> getSortedEntries(AbstractRStarTreeNode<?, ?> node, DBIDs ids) { - List<FCPair<D, SpatialEntry>> result = new ArrayList<>(); - - for(int i = 0; i < node.getNumEntries(); i++) { - SpatialEntry entry = node.getEntry(i); - D minMinDist = distanceQuery.getDistanceFactory().infiniteDistance(); - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - D minDist = distanceFunction.minDist(entry, relation.get(iter)); - tree.statistics.countDistanceCalculation(); - minMinDist = DistanceUtil.min(minDist, minMinDist); - } - result.add(new FCPair<>(minMinDist, entry)); - } - - Collections.sort(result); - return result; - } - - @Override - public KNNList<D> getKNNForObject(O obj, int k) { - final KNNHeap<D> knnList = DBIDUtil.newHeap(distanceFunction.getDistanceFactory(), k); - final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq = new ComparableMinHeap<>(Math.min(knnList.getK() << 1, 20)); - tree.statistics.countKNNQuery(); - - // push root - pq.add(new GenericDistanceSearchCandidate<>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); - D maxDist = distanceFunction.getDistanceFactory().infiniteDistance(); - - // search in tree - while(!pq.isEmpty()) { - GenericDistanceSearchCandidate<D> pqNode = pq.poll(); - - if(pqNode.mindist.compareTo(maxDist) > 0) { - break; - } - maxDist = expandNode(obj, knnList, pq, maxDist, pqNode.nodeID); - } - return knnList.toKNNList(); - } - - private D expandNode(O object, KNNHeap<D> knnList, final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq, D maxDist, final int nodeID) { - AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); - // data node - if(node.isLeaf()) { - for(int i = 0; i < node.getNumEntries(); i++) { - SpatialEntry entry = node.getEntry(i); - D distance = distanceFunction.minDist(entry, object); - tree.statistics.countDistanceCalculation(); - if(distance.compareTo(maxDist) <= 0) { - knnList.insert(distance, ((LeafEntry) entry).getDBID()); - maxDist = knnList.getKNNDistance(); - } - } - } - // directory node - else { - for(int i = 0; i < node.getNumEntries(); i++) { - SpatialEntry entry = node.getEntry(i); - D distance = distanceFunction.minDist(entry, object); - tree.statistics.countDistanceCalculation(); - // Greedy expand, bypassing the queue - if(distance.isNullDistance()) { - expandNode(object, knnList, pq, maxDist, ((DirectoryEntry) entry).getPageID()); - } - else { - if(distance.compareTo(maxDist) <= 0) { - pq.add(new GenericDistanceSearchCandidate<>(distance, ((DirectoryEntry) entry).getPageID())); - } - } - } - } - return maxDist; - } - - @Override - public List<KNNList<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { - // While this works, it seems to be slow at least for large sets! - final Map<DBID, KNNHeap<D>> knnLists = new HashMap<>(ids.size()); - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - knnLists.put(DBIDUtil.deref(iter), DBIDUtil.newHeap(distanceFunction.getDistanceFactory(), k)); - } - - batchNN(tree.getRoot(), knnLists); - - List<KNNList<D>> result = new ArrayList<>(); - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - tree.statistics.countKNNQuery(); - result.add(knnLists.get(DBIDUtil.deref(iter)).toKNNList()); - } - return result; - } -} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java deleted file mode 100644 index 16a3393a..00000000 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/GenericRStarTreeRangeQuery.java +++ /dev/null @@ -1,131 +0,0 @@ -package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2013 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; -import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; -import de.lmu.ifi.dbs.elki.index.tree.query.GenericDistanceSearchCandidate; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.ComparableMinHeap; -import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; - -/** - * Instance of a range query for a particular spatial index. - * - * Reference: - * <p> - * J. Kuan, P. Lewis<br /> - * Fast k nearest neighbour search for R-tree family<br /> - * In Proc. Int. Conf Information, Communications and Signal Processing, ICICS - * 1997 - * </p> - * - * @author Erich Schubert - * - * @apiviz.uses AbstractRStarTree - * @apiviz.uses SpatialPrimitiveDistanceFunction - */ -@Reference(authors = "J. Kuan, P. Lewis", title = "Fast k nearest neighbour search for R-tree family", booktitle = "Proc. Int. Conf Information, Communications and Signal Processing, ICICS 1997", url = "http://dx.doi.org/10.1109/ICICS.1997.652114") -public class GenericRStarTreeRangeQuery<O extends SpatialComparable, D extends Distance<D>> extends AbstractDistanceRangeQuery<O, D> { - /** - * The index to use - */ - protected final AbstractRStarTree<?, ?, ?> tree; - - /** - * Spatial primitive distance function - */ - protected final SpatialPrimitiveDistanceFunction<? super O, D> distanceFunction; - - /** - * Constructor. - * - * @param tree Index to use - * @param distanceQuery Distance query to use - */ - public GenericRStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery) { - super(distanceQuery); - this.tree = tree; - this.distanceFunction = distanceQuery.getDistanceFunction(); - } - - /** - * Perform the actual query process. - * - * @param object Query object - * @param epsilon Query range - * @return Objects contained in query range. - */ - protected DistanceDBIDList<D> doRangeQuery(O object, D epsilon) { - final GenericDistanceDBIDList<D> result = new GenericDistanceDBIDList<>(); - final ComparableMinHeap<GenericDistanceSearchCandidate<D>> pq = new ComparableMinHeap<>(); - tree.statistics.countRangeQuery(); - - // push root - pq.add(new GenericDistanceSearchCandidate<>(distanceFunction.getDistanceFactory().nullDistance(), tree.getRootID())); - - // search in tree - while(!pq.isEmpty()) { - GenericDistanceSearchCandidate<D> pqNode = pq.poll(); - if(pqNode.mindist.compareTo(epsilon) > 0) { - break; - } - - AbstractRStarTreeNode<?, ?> node = tree.getNode(pqNode.nodeID); - final int numEntries = node.getNumEntries(); - - for(int i = 0; i < numEntries; i++) { - D distance = distanceFunction.minDist(node.getEntry(i), object); - tree.statistics.countDistanceCalculation(); - if(distance.compareTo(epsilon) <= 0) { - if(node.isLeaf()) { - LeafEntry entry = (LeafEntry) node.getEntry(i); - result.add(distance, entry.getDBID()); - } - else { - DirectoryEntry entry = (DirectoryEntry) node.getEntry(i); - pq.add(new GenericDistanceSearchCandidate<>(distance, entry.getEntryID())); - } - } - } - } - - // sort the result according to the distances - result.sort(); - return result; - } - - @Override - public DistanceDBIDList<D> getRangeForObject(O obj, D range) { - return doRangeQuery(obj, range); - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeKNNQuery.java index 472e4b57..f0e6e01e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -34,16 +34,15 @@ import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; -import de.lmu.ifi.dbs.elki.database.ids.integer.DoubleDistanceIntegerDBIDKNNHeap; -import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.index.tree.DirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; import de.lmu.ifi.dbs.elki.index.tree.query.DoubleDistanceSearchCandidate; @@ -68,41 +67,56 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Erich Schubert * * @apiviz.uses AbstractRStarTree - * @apiviz.uses SpatialPrimitiveDoubleDistanceFunction + * @apiviz.uses SpatialPrimitiveDistanceFunction + * @apiviz.uses DoubleDistanceSearchCandidate */ -@Reference(authors = "G. R. Hjaltason, H. Samet", title = "Ranking in spatial databases", booktitle = "Advances in Spatial Databases - 4th Symposium, SSD'95", url = "http://dx.doi.org/10.1007/3-540-60159-7_6") -public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extends AbstractDistanceKNNQuery<O, DoubleDistance> { +@Reference(authors = "G. R. Hjaltason, H. Samet", // +title = "Ranking in spatial databases", // +booktitle = "Advances in Spatial Databases - 4th Symposium, SSD'95", // +url = "http://dx.doi.org/10.1007/3-540-60159-7_6") +public class RStarTreeKNNQuery<O extends SpatialComparable> implements KNNQuery<O> { /** * The index to use */ protected final AbstractRStarTree<?, ?, ?> tree; /** - * Spatial primitive distance function + * Spatial primitive distance function. */ - protected final SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction; + protected final SpatialPrimitiveDistanceFunction<? super O> distanceFunction; + + /** + * Relation we query. + */ + protected Relation<? extends O> relation; /** * Constructor. * * @param tree Index to use - * @param distanceQuery Distance query to use + * @param relation Data relation to query * @param distanceFunction Distance function */ - public DoubleDistanceRStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { - super(distanceQuery); + public RStarTreeKNNQuery(AbstractRStarTree<?, ?, ?> tree, Relation<? extends O> relation, SpatialPrimitiveDistanceFunction<? super O> distanceFunction) { + super(); + this.relation = relation; this.tree = tree; this.distanceFunction = distanceFunction; } @Override - public DoubleDistanceKNNList getKNNForObject(O obj, int k) { + public KNNList getKNNForDBID(DBIDRef id, int k) { + return getKNNForObject(relation.get(id), k); + } + + @Override + public KNNList getKNNForObject(O obj, int k) { if(k < 1) { throw new IllegalArgumentException("At least one neighbor has to be requested!"); } tree.statistics.countKNNQuery(); - final DoubleDistanceKNNHeap knnList = new DoubleDistanceIntegerDBIDKNNHeap(k); + final KNNHeap knnList = DBIDUtil.newHeap(k); final ComparableMinHeap<DoubleDistanceSearchCandidate> pq = new ComparableMinHeap<>(Math.min(knnList.getK() << 1, 21)); // expand root @@ -120,13 +134,13 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend return knnList.toKNNList(); } - private double expandNode(O object, DoubleDistanceKNNHeap knnList, final ComparableMinHeap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { + private double expandNode(O object, KNNHeap knnList, final ComparableMinHeap<DoubleDistanceSearchCandidate> pq, double maxDist, final int nodeID) { AbstractRStarTreeNode<?, ?> node = tree.getNode(nodeID); // data node if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialPointLeafEntry entry = (SpatialPointLeafEntry) node.getEntry(i); - double distance = distanceFunction.doubleMinDist(entry, object); + double distance = distanceFunction.minDist(entry, object); tree.statistics.countDistanceCalculation(); if(distance <= maxDist) { maxDist = knnList.insert(distance, entry.getDBID()); @@ -137,7 +151,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend else { for(int i = 0; i < node.getNumEntries(); i++) { SpatialDirectoryEntry entry = (SpatialDirectoryEntry) node.getEntry(i); - double distance = distanceFunction.doubleMinDist(entry, object); + double distance = distanceFunction.minDist(entry, object); tree.statistics.countDistanceCalculation(); // Greedy expand, bypassing the queue if(distance <= 0) { @@ -159,19 +173,19 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * @param node the node for which the query should be performed * @param knnLists a map containing the knn lists for each query objects */ - protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, DoubleDistanceKNNHeap> knnLists) { + protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap> knnLists) { if(node.isLeaf()) { for(int i = 0; i < node.getNumEntries(); i++) { SpatialEntry p = node.getEntry(i); - for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { + for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) { final DBID q = ent.getKey(); - final DoubleDistanceKNNHeap knns_q = ent.getValue(); - double knn_q_maxDist = knns_q.doubleKNNDistance(); + final KNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.getKNNDistance(); DBID pid = ((LeafEntry) p).getDBID(); // FIXME: objects are NOT accessible by DBID in a plain R-tree // context! - double dist_pq = distanceFunction.doubleDistance(relation.get(pid), relation.get(q)); + double dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q)); tree.statistics.countDistanceCalculation(); if(dist_pq <= knn_q_maxDist) { knns_q.insert(dist_pq, pid); @@ -187,9 +201,9 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend List<DoubleDistanceEntry> entries = getSortedEntries(node, ids); for(DoubleDistanceEntry distEntry : entries) { double minDist = distEntry.distance; - for(Entry<DBID, DoubleDistanceKNNHeap> ent : knnLists.entrySet()) { - final DoubleDistanceKNNHeap knns_q = ent.getValue(); - double knn_q_maxDist = knns_q.doubleKNNDistance(); + for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) { + final KNNHeap knns_q = ent.getValue(); + double knn_q_maxDist = knns_q.getKNNDistance(); if(minDist <= knn_q_maxDist) { SpatialEntry entry = distEntry.entry; @@ -217,7 +231,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend SpatialEntry entry = node.getEntry(i); double minMinDist = Double.MAX_VALUE; for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - double minDist = distanceFunction.doubleMinDist(entry, relation.get(iter)); + double minDist = distanceFunction.minDist(entry, relation.get(iter)); tree.statistics.countDistanceCalculation(); minMinDist = Math.min(minDist, minMinDist); } @@ -235,7 +249,7 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend * * @apiviz.hidden */ - class DoubleDistanceEntry implements Comparable<DoubleDistanceEntry> { + static class DoubleDistanceEntry implements Comparable<DoubleDistanceEntry> { /** * Referenced entry */ @@ -264,22 +278,22 @@ public class DoubleDistanceRStarTreeKNNQuery<O extends SpatialComparable> extend } @Override - public List<DoubleDistanceKNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(k < 1) { throw new IllegalArgumentException("At least one enumeration has to be requested!"); } // While this works, it seems to be slow at least for large sets! // TODO: use a DataStore instead of a map. - final Map<DBID, DoubleDistanceKNNHeap> knnLists = new HashMap<>(ids.size()); + final Map<DBID, KNNHeap> knnLists = new HashMap<>(ids.size()); for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); - knnLists.put(id, new DoubleDistanceIntegerDBIDKNNHeap(k)); + knnLists.put(id, DBIDUtil.newHeap(k)); } batchNN(tree.getRoot(), knnLists); - List<DoubleDistanceKNNList> result = new ArrayList<>(); + List<KNNList> result = new ArrayList<>(); for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { DBID id = DBIDUtil.deref(iter); tree.statistics.countKNNQuery(); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeRangeQuery.java index 4fe2719e..aad67fed 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/DoubleDistanceRStarTreeRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,13 +26,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; import java.util.Arrays; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDList; -import de.lmu.ifi.dbs.elki.database.ids.integer.DoubleDistanceIntegerDBIDList; -import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; -import de.lmu.ifi.dbs.elki.database.query.range.AbstractDistanceRangeQuery; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +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.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; @@ -53,10 +53,10 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @author Erich Schubert * * @apiviz.uses AbstractRStarTree - * @apiviz.uses SpatialPrimitiveDoubleDistanceFunction + * @apiviz.uses SpatialPrimitiveDistanceFunction */ @Reference(authors = "J. Kuan, P. Lewis", title = "Fast k nearest neighbour search for R-tree family", booktitle = "Proc. Int. Conf Information, Communications and Signal Processing, ICICS 1997", url = "http://dx.doi.org/10.1109/ICICS.1997.652114") -public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> extends AbstractDistanceRangeQuery<O, DoubleDistance> { +public class RStarTreeRangeQuery<O extends SpatialComparable> implements RangeQuery<O> { /** * The index to use */ @@ -65,31 +65,36 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte /** * Spatial primitive distance function */ - protected final SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction; + protected final SpatialPrimitiveDistanceFunction<? super O> distanceFunction; + + /** + * Relation we query. + */ + protected Relation<? extends O> relation; /** * Constructor. * * @param tree Index to use - * @param distanceQuery Distance query to use + * @param relation Data relation to query * @param distanceFunction Distance function */ - public DoubleDistanceRStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, DistanceQuery<O, DoubleDistance> distanceQuery, SpatialPrimitiveDoubleDistanceFunction<? super O> distanceFunction) { - super(distanceQuery); + public RStarTreeRangeQuery(AbstractRStarTree<?, ?, ?> tree, Relation<? extends O> relation, SpatialPrimitiveDistanceFunction<? super O> distanceFunction) { + super(); + this.relation = relation; this.tree = tree; this.distanceFunction = distanceFunction; } - /** - * Perform the actual query process. - * - * @param object Query object - * @param epsilon Query range - * @return Objects contained in query range. - */ - protected DoubleDistanceDBIDList doRangeQuery(O object, double epsilon) { + @Override + public DoubleDBIDList getRangeForDBID(DBIDRef id, double range) { + return getRangeForObject(relation.get(id), range); + } + + @Override + public DoubleDBIDList getRangeForObject(O obj, double range) { tree.statistics.countRangeQuery(); - final DoubleDistanceIntegerDBIDList result = new DoubleDistanceIntegerDBIDList(); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); // Processing queue. int[] pq = new int[101]; @@ -105,9 +110,9 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte if(node.isLeaf()) { for(int i = 0; i < numEntries; i++) { SpatialPointLeafEntry entry = (SpatialPointLeafEntry) node.getEntry(i); - double distance = distanceFunction.doubleMinDist(object, entry); + double distance = distanceFunction.minDist(obj, entry); tree.statistics.countDistanceCalculation(); - if(distance <= epsilon) { + if(distance <= range) { result.add(distance, entry.getDBID()); } } @@ -115,8 +120,8 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte else { for(int i = 0; i < numEntries; i++) { SpatialDirectoryEntry entry = (SpatialDirectoryEntry) node.getEntry(i); - double distance = distanceFunction.doubleMinDist(object, entry); - if(distance <= epsilon) { + double distance = distanceFunction.minDist(obj, entry); + if(distance <= range) { if(ps == pq.length) { pq = Arrays.copyOf(pq, pq.length + (pq.length >>> 1)); } @@ -130,9 +135,4 @@ public class DoubleDistanceRStarTreeRangeQuery<O extends SpatialComparable> exte result.sort(); return result; } - - @Override - public DistanceDBIDList<DoubleDistance> getRangeForObject(O obj, DoubleDistance range) { - return doRangeQuery(obj, range.doubleValue()); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java index 46c814ee..d76cb504 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/RStarTreeUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,15 +23,14 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; /** @@ -42,10 +41,8 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree; * @apiviz.landmark * * @apiviz.uses AbstractRStarTree - * @apiviz.uses DoubleDistanceRStarTreeKNNQuery - * @apiviz.uses DoubleDistanceRStarTreeRangeQuery - * @apiviz.uses GenericRStarTreeKNNQuery - * @apiviz.uses GenericRStarTreeRangeQuery + * @apiviz.uses EuclideanRStarTreeKNNQuery + * @apiviz.uses EuclideanRStarTreeRangeQuery * @apiviz.has RangeQuery * @apiviz.has KNNQuery */ @@ -55,24 +52,19 @@ public final class RStarTreeUtil { * 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 extends SpatialComparable, D extends Distance<D>> RangeQuery<O, D> getRangeQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { + public static <O extends SpatialComparable> RangeQuery<O> getRangeQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O> distanceQuery, Object... hints) { // Can we support this distance function - spatial distances only! - SpatialPrimitiveDistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); - // Can we use an optimized query? - if(df instanceof SpatialPrimitiveDoubleDistanceFunction) { - DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) DistanceQuery.class.cast(distanceQuery); - SpatialPrimitiveDoubleDistanceFunction<? super O> dfc = (SpatialPrimitiveDoubleDistanceFunction<? super O>) SpatialPrimitiveDoubleDistanceFunction.class.cast(df); - RangeQuery<O, ?> q = new DoubleDistanceRStarTreeRangeQuery<>(tree, dqc, dfc); - return (RangeQuery<O, D>) q; + SpatialPrimitiveDistanceFunction<? super O> df = distanceQuery.getDistanceFunction(); + if(EuclideanDistanceFunction.STATIC.equals(df)) { + return (RangeQuery<O>) new EuclideanRStarTreeRangeQuery<>(tree, (Relation<NumberVector>) distanceQuery.getRelation()); } - return new GenericRStarTreeRangeQuery<>(tree, distanceQuery); + return new RStarTreeRangeQuery<>(tree, distanceQuery.getRelation(), df); } /** @@ -80,23 +72,18 @@ public final class RStarTreeUtil { * 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 extends SpatialComparable, D extends Distance<D>> KNNQuery<O, D> getKNNQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O, D> distanceQuery, Object... hints) { + public static <O extends SpatialComparable> KNNQuery<O> getKNNQuery(AbstractRStarTree<?, ?, ?> tree, SpatialDistanceQuery<O> distanceQuery, Object... hints) { // Can we support this distance function - spatial distances only! - SpatialPrimitiveDistanceFunction<? super O, D> df = distanceQuery.getDistanceFunction(); - // Can we use an optimized query? - if(df instanceof SpatialPrimitiveDoubleDistanceFunction) { - DistanceQuery<O, DoubleDistance> dqc = (DistanceQuery<O, DoubleDistance>) DistanceQuery.class.cast(distanceQuery); - SpatialPrimitiveDoubleDistanceFunction<? super O> dfc = (SpatialPrimitiveDoubleDistanceFunction<? super O>) SpatialPrimitiveDoubleDistanceFunction.class.cast(df); - KNNQuery<O, ?> q = new DoubleDistanceRStarTreeKNNQuery<>(tree, dqc, dfc); - return (KNNQuery<O, D>) q; + SpatialPrimitiveDistanceFunction<? super O> df = distanceQuery.getDistanceFunction(); + if(EuclideanDistanceFunction.STATIC.equals(df)) { + return (KNNQuery<O>) new EuclideanRStarTreeKNNQuery<>(tree, (Relation<NumberVector>) distanceQuery.getRelation()); } - return new GenericRStarTreeKNNQuery<>(tree, distanceQuery); + return new RStarTreeKNNQuery<>(tree, distanceQuery.getRelation(), df); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java index 69bcd3d0..35dd34e7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/query/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java new file mode 100644 index 00000000..b824bc77 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java @@ -0,0 +1,129 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.io.IOException; +import java.io.ObjectInput; +import java.io.ObjectOutput; + +import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; + +/** + * Represents an entry in a directory node of an RdKNN-Tree. Additionally to a + * SpatialDirectoryEntry a RdKNNDirectoryEntry holds the knn distance of the + * underlying RdKNN-Tree node. + * + * @author Elke Achtert + * @param Distance type + */ +public class RdKNNDirectoryEntry extends SpatialDirectoryEntry implements RdKNNEntry { + private static final long serialVersionUID = 2; + + /** + * The aggregated knn distance of this entry. + */ + private double knnDistance; + + /** + * Empty constructor for serialization purposes. + */ + public RdKNNDirectoryEntry() { + // empty constructor + } + + /** + * Constructs a new RDkNNDirectoryEntry object with the given parameters. + * + * @param id the unique id of the underlying node + * @param mbr the minimum bounding rectangle of the underlying node + * @param knnDistance the aggregated knn distance of this entry + */ + public RdKNNDirectoryEntry(int id, ModifiableHyperBoundingBox mbr, double knnDistance) { + super(id, mbr); + this.knnDistance = knnDistance; + } + + @Override + public double getKnnDistance() { + return knnDistance; + } + + @Override + public void setKnnDistance(double knnDistance) { + this.knnDistance = knnDistance; + } + + /** + * Calls the super method and writes the knn distance of this entry to the + * specified stream. + * + * @param out the stream to write the object to + * @throws java.io.IOException Includes any I/O exceptions that may occur + */ + @Override + public void writeExternal(ObjectOutput out) throws IOException { + super.writeExternal(out); + out.writeDouble(knnDistance); + } + + /** + * Calls the super method and reads the knn distance of this entry from the + * specified input stream. + * + * @param in the stream to read data from in order to restore the object + * @throws java.io.IOException if I/O errors occur + * @throws ClassNotFoundException If the class for an object being restored + * cannot be found. + */ + @Override + public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { + super.readExternal(in); + this.knnDistance = in.readDouble(); + } + + /** + * Indicates whether some other object is "equal to" this one. + * + * @param o the object to be tested + * @return true, if the super method returns true and o is an + * RDkNNDirectoryEntry and has the same knnDistance as this entry. + */ + @Override + public boolean equals(Object o) { + if(this == o) { + return true; + } + if(o == null || getClass() != o.getClass()) { + return false; + } + if(!super.equals(o)) { + return false; + } + + final RdKNNDirectoryEntry that = (RdKNNDirectoryEntry) o; + + return knnDistance == that.knnDistance; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java new file mode 100644 index 00000000..f96a6419 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java @@ -0,0 +1,49 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.index.tree.spatial.SpatialEntry; + +/** + * Defines the requirements for an entry in an RdKNN-Tree node. Additionally to + * an entry in an R*-Tree an RDkNNEntry holds the knn distance of the underlying + * data object or RdKNN-Tree node. + * + * @author Elke Achtert + */ +interface RdKNNEntry extends SpatialEntry { + /** + * Returns the knn distance of this entry. + * + * @return the knn distance of this entry + */ + public double getKnnDistance(); + + /** + * Sets the knn distance of this entry. + * + * @param knnDistance the knn distance to be set + */ + public void setKnnDistance(double knnDistance); +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java new file mode 100644 index 00000000..6d665eb9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java @@ -0,0 +1,129 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.io.IOException; +import java.io.ObjectInput; +import java.io.ObjectOutput; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; + +/** + * Represents an entry in a leaf node of an RdKNN-Tree. Additionally to a + * SpatialLeafEntry a RdKNNLeafEntry holds the knn distance of the underlying + * data object. + * + * @author Elke Achtert + */ +public class RdKNNLeafEntry extends SpatialPointLeafEntry implements RdKNNEntry { + private static final long serialVersionUID = 2; + + /** + * The knn distance of the underlying data object. + */ + private double knnDistance; + + /** + * Empty constructor for serialization purposes. + */ + public RdKNNLeafEntry() { + super(); + } + + /** + * Constructs a new RDkNNLeafEntry object with the given parameters. + * + * @param id the unique id of the underlying data object + * @param vector the underlying data object + * @param knnDistance the knn distance of the underlying data object + */ + public RdKNNLeafEntry(DBID id, NumberVector vector, double knnDistance) { + super(id, vector); + this.knnDistance = knnDistance; + } + + @Override + public double getKnnDistance() { + return knnDistance; + } + + @Override + public void setKnnDistance(double knnDistance) { + this.knnDistance = knnDistance; + } + + /** + * Calls the super method and writes the knn distance of this entry to the + * specified stream. + * + * @param out the stream to write the object to + * @throws java.io.IOException Includes any I/O exceptions that may occur + */ + @Override + public void writeExternal(ObjectOutput out) throws IOException { + super.writeExternal(out); + out.writeDouble(knnDistance); + } + + /** + * Calls the super method and reads the knn distance of this entry from the + * specified input stream. + * + * @param in the stream to read data from in order to restore the object + * @throws java.io.IOException if I/O errors occur + * @throws ClassNotFoundException If the class for an object being restored + * cannot be found. + */ + @Override + public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { + super.readExternal(in); + this.knnDistance = in.readDouble(); + } + + /** + * Indicates whether some other object is "equal to" this one. + * + * @param o the object to be tested + * @return true, if the super method returns true and o is an RDkNNLeafEntry + * and has the same knnDistance as this entry. + */ + @Override + public boolean equals(Object o) { + if(this == o) { + return true; + } + if(o == null || getClass() != o.getClass()) { + return false; + } + if(!super.equals(o)) { + return false; + } + + final RdKNNLeafEntry that = (RdKNNLeafEntry) o; + + return knnDistance == that.knnDistance; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java new file mode 100644 index 00000000..89e231b4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java @@ -0,0 +1,96 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; + +/** + * Represents a node in a RDkNN-Tree. + * + * @author Elke Achtert + * + * @apiviz.has RdKNNEntry oneway - - contains + */ +public class RdKNNNode extends AbstractRStarTreeNode<RdKNNNode, RdKNNEntry> { + private static final long serialVersionUID = 1; + + /** + * Empty constructor for Externalizable interface. + */ + public RdKNNNode() { + // empty constructor + } + + /** + * Creates a new RdKNNNode object. + * + * @param capacity the capacity (maximum number of entries plus 1 for + * overflow) of this node + * @param isLeaf indicates whether this node is a leaf node + */ + public RdKNNNode(int capacity, boolean isLeaf) { + super(capacity, isLeaf, RdKNNEntry.class); + } + + /** + * Computes and returns the aggregated knn distance of this node + * + * @return the aggregated knn distance of this node + */ + protected double kNNDistance() { + double result = getEntry(0).getKnnDistance(); + for(int i = 1; i < getNumEntries(); i++) { + double knnDistance = getEntry(i).getKnnDistance(); + result = (result < knnDistance) ? knnDistance : result; + } + return result; + } + + @Override + public boolean adjustEntry(RdKNNEntry entry) { + boolean changed = super.adjustEntry(entry); + entry.setKnnDistance(kNNDistance()); + return changed; + } + + /** + * Tests, if the parameters of the entry representing this node, are correctly + * set. Subclasses may need to overwrite this method. + * + * @param parent the parent holding the entry representing this node + * @param index the index of the entry in the parents child array + */ + @Override + protected void integrityCheckParameters(RdKNNNode parent, int index) { + super.integrityCheckParameters(parent, index); + // test if knn distance is correctly set + RdKNNEntry entry = parent.getEntry(index); + double knnDistance = kNNDistance(); + if(entry.getKnnDistance() != knnDistance) { + double soll = knnDistance; + double ist = entry.getKnnDistance(); + throw new RuntimeException("Wrong knnDistance in node " + parent.getPageID() + " at index " + index + " (child " + entry + ")" + "\nsoll: " + soll + ",\n ist: " + ist); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java new file mode 100644 index 00000000..374e9592 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java @@ -0,0 +1,672 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; +import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.index.DynamicIndex; +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.IndexTreePath; +import de.lmu.ifi.dbs.elki.index.tree.LeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; + +/** + * RDkNNTree is a spatial index structure based on the concepts of the R*-Tree + * supporting efficient processing of reverse k nearest neighbor queries. The + * k-nn distance is stored in each entry of a node. + * <p/> + * TODO: noch nicht fertig!!! + * + * @author Elke Achtert + * + * @apiviz.has RdKNNNode + * @apiviz.has RdKNNTreeHeader + * + * @param <O> Object type + */ +// FIXME: currently does not yet return RKNNQuery objects! +public class RdKNNTree<O extends NumberVector> extends NonFlatRStarTree<RdKNNNode, RdKNNEntry, RdkNNSettings<O>> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O>, DynamicIndex { + /** + * The logger for this class. + */ + private static final Logging LOG = Logging.getLogger(RdKNNTree.class); + + /** + * The distance function. + */ + private SpatialDistanceQuery<O> distanceQuery; + + /** + * Internal knn query object, for updating the rKNN. + */ + protected KNNQuery<O> knnQuery; + + /** + * The relation we query. + */ + private Relation<O> relation; + + /** + * Constructor. + * + * @param relation Relation to index + * @param pagefile Data storage + * @param settings Tree settings + */ + public RdKNNTree(Relation<O> relation, PageFile<RdKNNNode> pagefile, RdkNNSettings<O> settings) { + super(pagefile, settings); + this.relation = relation; + this.distanceQuery = settings.distanceFunction.instantiate(relation); + this.knnQuery = relation.getDatabase().getKNNQuery(distanceQuery); + } + + /** + * Performs necessary operations before inserting the specified entry. + * + * @param entry the entry to be inserted + */ + @Override + protected void preInsert(RdKNNEntry entry) { + KNNHeap knns_o = DBIDUtil.newHeap(settings.k_max); + preInsert(entry, getRootEntry(), knns_o); + } + + /** + * Performs necessary operations after deleting the specified object. + */ + @Override + protected void postDelete(RdKNNEntry entry) { + // reverse knn of o + ModifiableDoubleDBIDList rnns = DBIDUtil.newDistanceDBIDList(); + doReverseKNN(getRoot(), ((RdKNNLeafEntry) entry).getDBID(), rnns); + + // knn of rnn + ArrayModifiableDBIDs ids = DBIDUtil.newArray(rnns); + ids.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(ids, settings.k_max); + + // adjust knn distances + adjustKNNDistance(getRootEntry(), ids, knnLists); + } + + /** + * Performs a bulk load on this RTree with the specified data. Is called by + * the constructor and should be overwritten by subclasses if necessary. + */ + @Override + protected void bulkLoad(List<RdKNNEntry> entries) { + super.bulkLoad(entries); + + // adjust all knn distances + ArrayModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); + for(RdKNNEntry entry : entries) { + DBID id = ((RdKNNLeafEntry) entry).getDBID(); + ids.add(id); + } + ids.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(ids, settings.k_max); + adjustKNNDistance(getRootEntry(), ids, knnLists); + + // test + doExtraIntegrityChecks(); + } + + public DoubleDBIDList reverseKNNQuery(DBID oid, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery) { + checkDistanceFunction(distanceFunction); + if(k > settings.k_max) { + throw new IllegalArgumentException("Parameter k is not supported, k > k_max: " + k + " > " + settings.k_max); + } + + // get candidates + ModifiableDoubleDBIDList candidates = DBIDUtil.newDistanceDBIDList(); + doReverseKNN(getRoot(), oid, candidates); + + if(k == settings.k_max) { + candidates.sort(); + return candidates; + } + + // refinement of candidates, if k < k_max + ArrayModifiableDBIDs candidateIDs = DBIDUtil.newArray(candidates); + candidateIDs.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(candidateIDs, k); + + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + int i = 0; + for(DBIDIter iter = candidateIDs.iter(); iter.valid(); iter.advance(), i++) { + for(DoubleDBIDListIter qr = knnLists.get(i).iter(); qr.valid(); qr.advance()) { + if(DBIDUtil.equal(oid, qr)) { + result.add(qr.doubleValue(), iter); + break; + } + } + } + + result.sort(); + return result; + } + + public List<ModifiableDoubleDBIDList> bulkReverseKNNQueryForID(DBIDs ids, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery) { + checkDistanceFunction(distanceFunction); + if(k > settings.k_max) { + throw new IllegalArgumentException("Parameter k is not supported, k > k_max: " + k + " > " + settings.k_max); + } + + // get candidates + Map<DBID, ModifiableDoubleDBIDList> candidateMap = new HashMap<>(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + candidateMap.put(id, DBIDUtil.newDistanceDBIDList()); + } + doBulkReverseKNN(getRoot(), ids, candidateMap); + + if(k == settings.k_max) { + List<ModifiableDoubleDBIDList> resultList = new ArrayList<>(); + for(ModifiableDoubleDBIDList candidates : candidateMap.values()) { + candidates.sort(); + resultList.add(candidates); + } + return resultList; + } + + // refinement of candidates, if k < k_max + // perform a knn query for the candidates + ArrayModifiableDBIDs candidateIDs = DBIDUtil.newArray(); + for(ModifiableDoubleDBIDList candidates : candidateMap.values()) { + candidateIDs.addDBIDs(candidates); + } + candidateIDs.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(candidateIDs, k); + + // and add candidate c to the result if o is a knn of c + List<ModifiableDoubleDBIDList> resultList = new ArrayList<>(); + for(DBID id : candidateMap.keySet()) { + ModifiableDoubleDBIDList candidates = candidateMap.get(id); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + for(DoubleDBIDListIter candidate = candidates.iter(); candidate.valid(); candidate.advance()) { + int pos = candidateIDs.binarySearch(candidate); + assert (pos >= 0); + for(DoubleDBIDListIter qr = knnLists.get(pos).iter(); qr.valid(); qr.advance()) { + if(DBIDUtil.equal(id, qr)) { + result.add(qr.doubleValue(), candidate); + break; + } + } + } + resultList.add(result); + } + return resultList; + } + + @Override + protected TreeIndexHeader createHeader() { + return new RdKNNTreeHeader(getPageSize(), dirCapacity, leafCapacity, dirMinimum, leafCapacity, settings.k_max); + } + + @Override + protected void initializeCapacities(RdKNNEntry exampleLeaf) { + int dimensionality = exampleLeaf.getDimensionality(); + int distanceSize = ByteArrayUtil.SIZE_DOUBLE; + + // overhead = index(4), numEntries(4), parentID(4), id(4), isLeaf(0.125) + double overhead = 16.125; + if(getPageSize() - overhead < 0) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + // dirCapacity = (pageSize - overhead) / (childID + childMBR + knnDistance) + // + 1 + dirCapacity = (int) ((getPageSize() - overhead) / (4 + 16 * dimensionality + distanceSize)) + 1; + + if(dirCapacity <= 1) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + if(dirCapacity < 10) { + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + } + + // minimum entries per directory node + dirMinimum = (int) Math.round((dirCapacity - 1) * 0.5); + if(dirMinimum < 2) { + dirMinimum = 2; + } + + // leafCapacity = (pageSize - overhead) / (childID + childValues + + // knnDistance) + 1 + leafCapacity = (int) ((getPageSize() - overhead) / (4 + 8 * dimensionality + distanceSize)) + 1; + + if(leafCapacity <= 1) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + if(leafCapacity < 10) { + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + } + + // minimum entries per leaf node + leafMinimum = (int) Math.round((leafCapacity - 1) * 0.5); + if(leafMinimum < 2) { + leafMinimum = 2; + } + + if(LOG.isVerbose()) { + LOG.verbose("Directory Capacity: " + dirCapacity + "\nLeaf Capacity: " + leafCapacity); + } + } + + /** + * Sorts the entries of the specified node according to their minimum distance + * to the specified object. + * + * @param node the node + * @param q the query object + * @param distanceFunction the distance function for computing the distances + * @return a list of the sorted entries + */ + // TODO: move somewhere else? + protected List<DoubleObjPair<RdKNNEntry>> getSortedEntries(AbstractRStarTreeNode<?, ?> node, SpatialComparable q, SpatialPrimitiveDistanceFunction<?> distanceFunction) { + List<DoubleObjPair<RdKNNEntry>> result = new ArrayList<>(); + + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry entry = (RdKNNEntry) node.getEntry(i); + double minDist = distanceFunction.minDist(entry, q); + result.add(new DoubleObjPair<>(minDist, entry)); + } + + Collections.sort(result); + return result; + } + + /** + * Adapts the knn distances before insertion of entry q. + * + * @param q the entry to be inserted + * @param nodeEntry the entry representing the root of the current subtree + * @param knns_q the knns of q + */ + private void preInsert(RdKNNEntry q, RdKNNEntry nodeEntry, KNNHeap knns_q) { + double knnDist_q = knns_q.getKNNDistance(); + RdKNNNode node = getNode(nodeEntry); + double knnDist_node = 0.; + + // leaf node + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry p = (RdKNNLeafEntry) node.getEntry(i); + double dist_pq = distanceQuery.distance(p.getDBID(), ((LeafEntry) q).getDBID()); + + // p is nearer to q than the farthest kNN-candidate of q + // ==> p becomes a knn-candidate + if(dist_pq <= knnDist_q) { + knns_q.insert(dist_pq, p.getDBID()); + if(knns_q.size() >= settings.k_max) { + knnDist_q = knns_q.getKNNDistance(); + q.setKnnDistance(knnDist_q); + } + + } + // p is nearer to q than to its farthest knn-candidate + // q becomes knn of p + if(dist_pq <= p.getKnnDistance()) { + O obj = relation.get(p.getDBID()); + KNNList knns_without_q = knnQuery.getKNNForObject(obj, settings.k_max); + + if(knns_without_q.size() + 1 < settings.k_max) { + p.setKnnDistance(Double.NaN); + } + else { + double knnDist_p = Math.min(knns_without_q.get(knns_without_q.size() - 1).doubleValue(), dist_pq); + p.setKnnDistance(knnDist_p); + } + } + knnDist_node = Math.max(knnDist_node, p.getKnnDistance()); + } + } + // directory node + else { + O obj = relation.get(((LeafEntry) q).getDBID()); + List<DoubleObjPair<RdKNNEntry>> entries = getSortedEntries(node, obj, settings.distanceFunction); + for(DoubleObjPair<RdKNNEntry> distEntry : entries) { + RdKNNEntry entry = distEntry.second; + double entry_knnDist = entry.getKnnDistance(); + + if(distEntry.first < entry_knnDist || distEntry.first < knnDist_q) { + preInsert(q, entry, knns_q); + knnDist_q = knns_q.getKNNDistance(); + } + knnDist_node = Math.max(knnDist_node, entry.getKnnDistance()); + } + } + nodeEntry.setKnnDistance(knnDist_node); + } + + /** + * Performs a reverse knn query in the specified subtree. + * + * @param node the root node of the current subtree + * @param oid the id of the object for which the rknn query is performed + * @param result the list containing the query results + */ + private void doReverseKNN(RdKNNNode node, DBID oid, ModifiableDoubleDBIDList result) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry entry = (RdKNNLeafEntry) node.getEntry(i); + double distance = distanceQuery.distance(entry.getDBID(), oid); + if(distance <= entry.getKnnDistance()) { + result.add(distance, entry.getDBID()); + } + } + } + // node is a inner node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNDirectoryEntry entry = (RdKNNDirectoryEntry) node.getEntry(i); + double minDist = distanceQuery.minDist(entry, oid); + if(minDist <= entry.getKnnDistance()) { + doReverseKNN(getNode(entry), oid, result); + } + } + } + } + + /** + * Performs a bulk reverse knn query in the specified subtree. + * + * @param node the root node of the current subtree + * @param ids the object ids for which the rknn query is performed + * @param result the map containing the query results for each object + */ + private void doBulkReverseKNN(RdKNNNode node, DBIDs ids, Map<DBID, ModifiableDoubleDBIDList> result) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry entry = (RdKNNLeafEntry) node.getEntry(i); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + double distance = distanceQuery.distance(entry.getDBID(), id); + if(distance <= entry.getKnnDistance()) { + result.get(id).add(distance, entry.getDBID()); + } + } + } + } + // node is a inner node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNDirectoryEntry entry = (RdKNNDirectoryEntry) node.getEntry(i); + ModifiableDBIDs candidates = DBIDUtil.newArray(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + double minDist = distanceQuery.minDist(entry, id); + if(minDist <= entry.getKnnDistance()) { + candidates.add(id); + } + if(!candidates.isEmpty()) { + doBulkReverseKNN(getNode(entry), candidates, result); + } + } + } + } + } + + /** + * Adjusts the knn distance in the subtree of the specified root entry. + * + * @param entry the root entry of the current subtree + * @param ids <em>Sorted</em> list of IDs + * @param knnLists a map of knn lists for each leaf entry + */ + private void adjustKNNDistance(RdKNNEntry entry, ArrayDBIDs ids, List<? extends KNNList> knnLists) { + RdKNNNode node = getNode(entry); + double knnDist_node = 0.; + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry leafEntry = node.getEntry(i); + DBID id = ((LeafEntry) leafEntry).getDBID(); + int pos = ids.binarySearch(id); + if(pos >= 0) { + leafEntry.setKnnDistance(knnLists.get(pos).getKNNDistance()); + } + knnDist_node = Math.max(knnDist_node, leafEntry.getKnnDistance()); + } + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry dirEntry = node.getEntry(i); + adjustKNNDistance(dirEntry, ids, knnLists); + knnDist_node = Math.max(knnDist_node, dirEntry.getKnnDistance()); + } + } + entry.setKnnDistance(knnDist_node); + } + + /** + * Creates a new leaf node with the specified capacity. + * + * @return a new leaf node + */ + @Override + protected RdKNNNode createNewLeafNode() { + return new RdKNNNode(leafCapacity, true); + } + + /** + * Creates a new directory node with the specified capacity. + * + * @return a new directory node + */ + @Override + protected RdKNNNode createNewDirectoryNode() { + return new RdKNNNode(dirCapacity, false); + } + + /** + * Creates a new directory entry representing the specified node. + * + * @param node the node to be represented by the new entry + */ + @Override + protected RdKNNEntry createNewDirectoryEntry(RdKNNNode node) { + return new RdKNNDirectoryEntry(node.getPageID(), node.computeMBR(), node.kNNDistance()); + } + + /** + * Creates an entry representing the root node. + * + * @return an entry representing the root node + */ + @Override + protected RdKNNEntry createRootEntry() { + return new RdKNNDirectoryEntry(0, null, Double.NaN); + } + + /** + * Throws an IllegalArgumentException if the specified distance function is + * not an instance of the distance function used by this index. + * + * @throws IllegalArgumentException + * @param distanceFunction the distance function to be checked + */ + private void checkDistanceFunction(SpatialPrimitiveDistanceFunction<? super O> distanceFunction) { + if(!settings.distanceFunction.equals(distanceFunction)) { + throw new IllegalArgumentException("Parameter distanceFunction must be an instance of " + this.distanceQuery.getClass() + ", but is " + distanceFunction.getClass()); + } + } + + protected RdKNNLeafEntry createNewLeafEntry(DBID id) { + return new RdKNNLeafEntry(id, relation.get(id), Double.NaN); + } + + @Override + public void initialize() { + super.initialize(); + insertAll(relation.getDBIDs()); + } + + /** + * Inserts the specified real vector object into this index. + * + * @param id the object id that was inserted + */ + @Override + public final void insert(DBIDRef id) { + insertLeaf(createNewLeafEntry(DBIDUtil.deref(id))); + } + + /** + * Inserts the specified objects into this index. If a bulk load mode is + * implemented, the objects are inserted in one bulk. + * + * @param ids the objects to be inserted + */ + @Override + public final void insertAll(DBIDs ids) { + if(ids.isEmpty() || (ids.size() == 1)) { + return; + } + + // Make an example leaf + if(canBulkLoad()) { + List<RdKNNEntry> leafs = new ArrayList<>(ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); + } + bulkLoad(leafs); + } + else { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + insert(iter); + } + } + + doExtraIntegrityChecks(); + } + + /** + * Deletes the specified object from this index. + * + * @return true if this index did contain the object with the specified id, + * false otherwise + */ + @Override + public final boolean delete(DBIDRef id) { + // find the leaf node containing o + O obj = relation.get(id); + IndexTreePath<RdKNNEntry> deletionPath = findPathToObject(getRootPath(), obj, id); + if(deletionPath == null) { + return false; + } + deletePath(deletionPath); + return true; + } + + @Override + public void deleteAll(DBIDs ids) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + delete(DBIDUtil.deref(iter)); + } + } + + @Override + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // Query on the relation we index + if(distanceQuery.getRelation() != relation) { + return null; + } + // Can we support this distance function - spatial distances only! + if(!(distanceQuery instanceof SpatialDistanceQuery)) { + return null; + } + return RStarTreeUtil.getRangeQuery(this, (SpatialDistanceQuery<O>) distanceQuery, hints); + } + + @Override + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // Query on the relation we index + if(distanceQuery.getRelation() != relation) { + return null; + } + // Can we support this distance function - spatial distances only! + if(!(distanceQuery instanceof SpatialDistanceQuery)) { + return null; + } + return RStarTreeUtil.getKNNQuery(this, (SpatialDistanceQuery<O>) distanceQuery, hints); + } + + @Override + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // FIXME: re-add + return null; + } + + @Override + public String getLongName() { + return "RdKNNTree"; + } + + @Override + public String getShortName() { + return "rdknntree"; + } + + @Override + protected Logging getLogger() { + return LOG; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java new file mode 100644 index 00000000..a2c9d110 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java @@ -0,0 +1,120 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeFactory; +import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; +import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; + +/** + * Factory for RdKNN R*-Trees. + * + * @author Erich Schubert + * + * @apiviz.stereotype factory + * @apiviz.uses RdKNNTreeIndex oneway - - «create» + * + * @param <O> Object type + */ +public class RdKNNTreeFactory<O extends NumberVector> extends AbstractRStarTreeFactory<O, RdKNNNode, RdKNNEntry, RdKNNTree<O>, RdkNNSettings<O>> { + /** + * Parameter for k + */ + public static final OptionID K_ID = new OptionID("rdknn.k", "positive integer specifying the maximal number k of reverse " + "k nearest neighbors to be supported."); + + /** + * The default distance function. + */ + public static final Class<?> DEFAULT_DISTANCE_FUNCTION = EuclideanDistanceFunction.class; + + /** + * Parameter for distance function + */ + public static final OptionID DISTANCE_FUNCTION_ID = new OptionID("rdknn.distancefunction", "Distance function to determine the distance between database objects."); + + /** + * Constructor. + * + * @param pageFileFactory Data storage + * @param settings Settings class + */ + public RdKNNTreeFactory(PageFileFactory<?> pageFileFactory, RdkNNSettings<O> settings) { + super(pageFileFactory, settings); + } + + @Override + public RdKNNTree<O> instantiate(Relation<O> relation) { + PageFile<RdKNNNode> pagefile = makePageFile(getNodeClass()); + RdKNNTree<O> index = new RdKNNTree<>(relation, pagefile, settings); + return index; + } + + protected Class<RdKNNNode> getNodeClass() { + return ClassGenericsUtil.uglyCastIntoSubclass(RdKNNNode.class); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer<O extends NumberVector> extends AbstractRStarTreeFactory.Parameterizer<O, RdkNNSettings<O>> { + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + IntParameter k_maxP = new IntParameter(K_ID); + k_maxP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT); + if(config.grab(k_maxP)) { + settings.k_max = k_maxP.intValue(); + } + + ObjectParameter<SpatialPrimitiveDistanceFunction<O>> distanceFunctionP = new ObjectParameter<>(DISTANCE_FUNCTION_ID, SpatialPrimitiveDistanceFunction.class, DEFAULT_DISTANCE_FUNCTION); + if(config.grab(distanceFunctionP)) { + settings.distanceFunction = distanceFunctionP.instantiateClass(config); + } + } + + @Override + protected RdKNNTreeFactory<O> makeInstance() { + return new RdKNNTreeFactory<>(pageFileFactory, settings); + } + + @Override + protected RdkNNSettings<O> createSettings() { + return new RdkNNSettings<>(); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java new file mode 100644 index 00000000..fdcff104 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java @@ -0,0 +1,101 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.io.IOException; +import java.io.RandomAccessFile; + +import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; + +/** + * Encapsulates the header information of a RDkNN-Tree. This information is + * needed for persistent storage. + * + * @author Elke Achtert + */ +class RdKNNTreeHeader extends TreeIndexHeader { + /** + * The size of this header in Bytes, which is 4 Bytes (for {@link #k_max}). + */ + private static int SIZE = 4; + + /** + * The maximum number k of reverse kNN queries to be supported. + */ + int k_max; + + /** + * Empty constructor for serialization. + */ + public RdKNNTreeHeader() { + super(); + } + + /** + * Creates a new header with the specified parameters. + * + * @param pageSize the size of a page in bytes + * @param dirCapacity the maximum number of entries in a directory node + * @param leafCapacity the maximum number of entries in a leaf node + * @param dirMinimum the minimum number of entries in a directory node + * @param leafMinimum the minimum number of entries in a leaf node + * @param k_max the maximum number k of reverse kNN queries to be supported + */ + public RdKNNTreeHeader(int pageSize, int dirCapacity, int leafCapacity, int dirMinimum, int leafMinimum, int k_max) { + super(pageSize, dirCapacity, leafCapacity, dirMinimum, leafMinimum); + this.k_max = k_max; + } + + /** + * Initializes this header from the specified file. Calls + * {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#readHeader(java.io.RandomAccessFile) + * TreeIndexHeader#readHeader(file)} and reads additionally the integer value + * of {@link #k_max} from the file. + */ + @Override + public void readHeader(RandomAccessFile file) throws IOException { + super.readHeader(file); + this.k_max = file.readInt(); + } + + /** + * Writes this header to the specified file. Calls + * {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#writeHeader(java.io.RandomAccessFile)} + * and writes additionally the integer value of {@link #k_max} to the file. + */ + @Override + public void writeHeader(RandomAccessFile file) throws IOException { + super.writeHeader(file); + file.writeInt(this.k_max); + } + + /** + * Returns {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#size()} plus + * the value of {@link #SIZE}). + */ + @Override + public int size() { + return super.size() + SIZE; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java new file mode 100644 index 00000000..3f9997e2 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java @@ -0,0 +1,46 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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.data.NumberVector; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; + +/** + * Settings for the RdKNN Tree. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public class RdkNNSettings<O extends NumberVector> extends AbstractRTreeSettings { + /** + * Parameter k. + */ + int k_max; + + /** + * The distance function. + */ + SpatialPrimitiveDistanceFunction<O> distanceFunction; +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java new file mode 100644 index 00000000..972376d6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>{@link de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree}</p> + */ +/* +This file is part of ELKI: +Environment for Developing KDD-Applications Supported by Index-Structures + +Copyright (C) 2014 +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/>. +*/ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn;
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java index 1c2a7fe8..f7ee9bb5 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTree.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java index 72f7f7dd..74a6f54d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -43,7 +43,7 @@ import de.lmu.ifi.dbs.elki.utilities.Alias; * @param <O> Object type */ @Alias({"rstar", "r*"}) -public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>, AbstractRTreeSettings> { +public class RStarTreeFactory<O extends NumberVector> extends AbstractRStarTreeFactory<O, RStarTreeNode, SpatialEntry, RStarTreeIndex<O>, AbstractRTreeSettings> { /** * Constructor. * @@ -73,7 +73,7 @@ public class RStarTreeFactory<O extends NumberVector<?>> extends AbstractRStarTr * * @param <O> Object type */ - public static class Parameterizer<O extends NumberVector<?>> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { + public static class Parameterizer<O extends NumberVector> extends AbstractRStarTreeFactory.Parameterizer<O, AbstractRTreeSettings> { @Override protected RStarTreeFactory<O> makeInstance() { return new RStarTreeFactory<>(pageFileFactory, settings); diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java index 15b43e64..f94d20dd 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeIndex.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -36,7 +36,6 @@ import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.DynamicIndex; import de.lmu.ifi.dbs.elki.index.KNNIndex; import de.lmu.ifi.dbs.elki.index.RangeIndex; @@ -55,7 +54,7 @@ import de.lmu.ifi.dbs.elki.persistent.PageFile; * * @param <O> Object type */ -public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { +public class RStarTreeIndex<O extends NumberVector> extends RStarTree implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { /** * The appropriate logger for this index. */ @@ -93,7 +92,7 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme super.initialize(); insertAll(relation.getDBIDs()); // Will check for actual bulk load! } - + /** * Inserts the specified reel vector object into this index. * @@ -119,13 +118,13 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme // Make an example leaf if(canBulkLoad()) { List<SpatialEntry> leafs = new ArrayList<>(ids.size()); - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { leafs.add(createNewLeafEntry(iter)); } bulkLoad(leafs); } else { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { insert(DBIDUtil.deref(iter)); } } @@ -153,13 +152,13 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme @Override public void deleteAll(DBIDs ids) { - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { delete(iter); } } @Override - public <D extends Distance<D>> RangeQuery<O, D> getRangeQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { + public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if(distanceQuery.getRelation() != relation) { return null; @@ -168,12 +167,12 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme if(!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } - SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; return RStarTreeUtil.getRangeQuery(this, dq, hints); } @Override - public <D extends Distance<D>> KNNQuery<O, D> getKNNQuery(DistanceQuery<O, D> distanceQuery, Object... hints) { + public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { // Query on the relation we index if(distanceQuery.getRelation() != relation) { return null; @@ -182,7 +181,7 @@ public class RStarTreeIndex<O extends NumberVector<?>> extends RStarTree impleme if(!(distanceQuery instanceof SpatialDistanceQuery)) { return null; } - SpatialDistanceQuery<O, D> dq = (SpatialDistanceQuery<O, D>) distanceQuery; + SpatialDistanceQuery<O> dq = (SpatialDistanceQuery<O>) distanceQuery; return RStarTreeUtil.getKNNQuery(this, dq, hints); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java index 7226fa1c..833b32d0 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/RStarTreeNode.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java index 7897fae1..8d8b2355 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java index 7d463a03..6f656be6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java @@ -7,7 +7,7 @@ import java.util.List; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java index fbbf7d8f..5794bc0d 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AdaptiveSortTileRecursiveBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java index c32a512c..d42f03e2 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -26,14 +26,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; import java.util.List; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable; /** * Interface for a bulk split strategy. * * @author Erich Schubert */ -public interface BulkSplit extends Parameterizable { +public interface BulkSplit { /** * Partitions the specified feature vectors * diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java index 8b0dfd77..77aaf071 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java index 5251e18b..edf11285 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java index 6bf37642..8852bffa 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionSortTileRecursiveBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java index 5d2083b3..f691789e 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java index 6cd7a598..a5431819 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java index 6e2b6369..b99764ab 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java index 5c52de3e..e2e2e593 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java index 01dde189..fe9698ba 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/ApproximativeLeastOverlapInsertionStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java index 837f0312..ac055184 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/CombinedInsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java index 477f0f48..964bce27 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/InsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,14 +24,13 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable; /** * RTree insertion strategy interface. * * @author Erich Schubert */ -public interface InsertionStrategy extends Parameterizable { +public interface InsertionStrategy { /** * Choose insertion rectangle. * diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java index 39348bf5..93d80436 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementInsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java index 627428e9..cf1267f7 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastEnlargementWithAreaInsertionStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java index 18855d90..8ed0b2b1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/LeastOverlapInsertionStrategy.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java index d425c7bd..6c2f26b2 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/insert/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java index 0af90d78..b7184f93 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/LimitedReinsertOverflowTreatment.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java index 4b2f94b1..06dcd215 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/OverflowTreatment.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java index 82ceb4ef..5aea9e5c 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/SplitOnlyOverflowTreatment.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java index fc7f16f0..28cbc3eb 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/overflow/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java index 7d2dfc0a..d3b6de11 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java index f73699ea..02b98e3b 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,7 +23,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; @@ -47,7 +47,7 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { /** * Distance function to use for measuring */ - SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction; + SpatialPrimitiveDistanceFunction<?> distanceFunction; /** * Constructor. @@ -55,7 +55,7 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { * @param reinsertAmount Relative amount of objects to reinsert. * @param distanceFunction Distance function to use */ - public AbstractPartialReinsert(double reinsertAmount, SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction) { + public AbstractPartialReinsert(double reinsertAmount, SpatialPrimitiveDistanceFunction<?> distanceFunction) { super(); this.reinsertAmount = reinsertAmount; this.distanceFunction = distanceFunction; @@ -87,7 +87,7 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { /** * Distance function to use for measuring */ - SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction; + SpatialPrimitiveDistanceFunction<?> distanceFunction; @Override protected void makeOptions(Parameterization config) { @@ -98,7 +98,7 @@ public abstract class AbstractPartialReinsert implements ReinsertStrategy { if(config.grab(reinsertAmountP)) { reinsertAmount = reinsertAmountP.getValue(); } - ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); + ObjectParameter<SpatialPrimitiveDistanceFunction<?>> distanceP = new ObjectParameter<>(REINSERT_DISTANCE_ID, SpatialPrimitiveDistanceFunction.class, SquaredEuclideanDistanceFunction.class); if(config.grab(distanceP)) { distanceFunction = distanceP.instantiateClass(config); } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java index 3002f18b..05dcffb9 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java @@ -6,7 +6,7 @@ import java.util.Collections; import de.lmu.ifi.dbs.elki.data.DoubleVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.data.spatial.SpatialUtil; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; @@ -15,7 +15,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,24 +42,27 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; * * @author Erich Schubert */ -@Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", title = "The R*-tree: an efficient and robust access method for points and rectangles", booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", url = "http://dx.doi.org/10.1145/93597.98741") +@Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", // +title = "The R*-tree: an efficient and robust access method for points and rectangles", // +booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", // +url = "http://dx.doi.org/10.1145/93597.98741") public class CloseReinsert extends AbstractPartialReinsert { /** * Constructor. - * + * * @param reinsertAmount Amount of objects to reinsert * @param distanceFunction Distance function to use for reinsertion */ - public CloseReinsert(double reinsertAmount, SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction) { + public CloseReinsert(double reinsertAmount, SpatialPrimitiveDistanceFunction<?> distanceFunction) { super(reinsertAmount, distanceFunction); } @Override public <A> int[] computeReinserts(A entries, ArrayAdapter<? extends SpatialComparable, ? super A> getter, SpatialComparable page) { DoubleIntPair[] order = new DoubleIntPair[getter.size(entries)]; - DoubleVector centroid = new DoubleVector(SpatialUtil.centroid(page)); + DoubleVector centroid = new DoubleVector(SpatialUtil.centroid(page)); for(int i = 0; i < order.length; i++) { - double distance = distanceFunction.doubleMinDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); + double distance = distanceFunction.minDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); order[i] = new DoubleIntPair(distance, i); } Arrays.sort(order, Collections.reverseOrder()); @@ -71,7 +74,7 @@ public class CloseReinsert extends AbstractPartialReinsert { } return re; } - + /** * Parameterization class. * @@ -81,7 +84,7 @@ public class CloseReinsert extends AbstractPartialReinsert { */ public static class Parameterizer extends AbstractPartialReinsert.Parameterizer { @Override - protected Object makeInstance() { + protected CloseReinsert makeInstance() { return new CloseReinsert(reinsertAmount, distanceFunction); } } diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java index 02c1d4d7..bdb7790a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java @@ -6,7 +6,7 @@ import java.util.Collections; import de.lmu.ifi.dbs.elki.data.DoubleVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.data.spatial.SpatialUtil; -import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; @@ -15,7 +15,7 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,7 +42,10 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; * * @author Erich Schubert */ -@Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", title = "The R*-tree: an efficient and robust access method for points and rectangles", booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", url = "http://dx.doi.org/10.1145/93597.98741") +@Reference(authors = "N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger", // +title = "The R*-tree: an efficient and robust access method for points and rectangles", // +booktitle = "Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990", // +url = "http://dx.doi.org/10.1145/93597.98741") public class FarReinsert extends AbstractPartialReinsert { /** * Constructor. @@ -50,7 +53,7 @@ public class FarReinsert extends AbstractPartialReinsert { * @param reinsertAmount Amount to reinsert * @param distanceFunction Distance function */ - public FarReinsert(double reinsertAmount, SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction) { + public FarReinsert(double reinsertAmount, SpatialPrimitiveDistanceFunction<?> distanceFunction) { super(reinsertAmount, distanceFunction); } @@ -59,7 +62,7 @@ public class FarReinsert extends AbstractPartialReinsert { DoubleIntPair[] order = new DoubleIntPair[getter.size(entries)]; DoubleVector centroid = new DoubleVector(SpatialUtil.centroid(page)); for(int i = 0; i < order.length; i++) { - double distance = distanceFunction.doubleMinDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); + double distance = distanceFunction.minDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); order[i] = new DoubleIntPair(distance, i); } Arrays.sort(order, Collections.reverseOrder()); @@ -81,8 +84,8 @@ public class FarReinsert extends AbstractPartialReinsert { */ public static class Parameterizer extends AbstractPartialReinsert.Parameterizer { @Override - protected Object makeInstance() { - return new CloseReinsert(reinsertAmount, distanceFunction); + protected FarReinsert makeInstance() { + return new FarReinsert(reinsertAmount, distanceFunction); } } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java index 2a4f130f..4b350123 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java index 2d2c6871..e96642f6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java index c31abc2d..60ba9457 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/AngTanLinearSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java index d00479cf..5bee1302 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/GreeneSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java index 4dc9b15d..75f37a71 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeLinearSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java index 91ef8f16..2ac7c176 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/RTreeQuadraticSplit.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java index 0bc1ffcf..0bd4f39f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/SplitStrategy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,14 +27,13 @@ import java.util.BitSet; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayAdapter; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable; /** * Generic interface for split strategies. * * @author Erich Schubert */ -public interface SplitStrategy extends Parameterizable { +public interface SplitStrategy { /** * Split a page * diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java index dc9092ad..259c83b1 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/TopologicalSplitter.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java index bb8cb1e2..78bffb0f 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/split/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java index def824ba..86cb360a 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/NodeArrayAdapter.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java index 22088417..6f2686f6 100644 --- a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/util/package-info.java @@ -6,7 +6,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |