diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert')
5 files changed, 351 insertions, 0 deletions
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 new file mode 100644 index 00000000..e0277606 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/AbstractPartialReinsert.java @@ -0,0 +1,105 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + 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.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SquaredEuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; + +/** + * Abstract base class for reinsertion strategies that have a "relative amount" + * parameter to partially reinsert entries. + * + * @author Erich Schubert + */ +public abstract class AbstractPartialReinsert implements ReinsertStrategy { + /** + * Amount of entries to reinsert + */ + protected double reinsertAmount = 0.3; + + /** + * Distance function to use for measuring + */ + SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction; + + /** + * Constructor. + * + * @param reinsertAmount Relative amount of objects to reinsert. + * @param distanceFunction Distance function to use + */ + public AbstractPartialReinsert(double reinsertAmount, SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction) { + super(); + this.reinsertAmount = reinsertAmount; + this.distanceFunction = distanceFunction; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static abstract class Parameterizer extends AbstractParameterizer { + /** + * Reinsertion share + */ + public static OptionID REINSERT_AMOUNT_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-amount", "The amount of entries to reinsert."); + + /** + * Reinsertion share + */ + public static OptionID REINSERT_DISTANCE_ID = OptionID.getOrCreateOptionID("rtree.reinsertion-distancce", "The distance function to compute reinsertion candidates by."); + + /** + * The actual reinsertion strategy + */ + double reinsertAmount = 0.3; + + /** + * Distance function to use for measuring + */ + SpatialPrimitiveDoubleDistanceFunction<?> distanceFunction; + + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + DoubleParameter reinsertAmountP = new DoubleParameter(REINSERT_AMOUNT_ID, new IntervalConstraint(0.0, IntervalConstraint.IntervalBoundary.OPEN, 0.5, IntervalConstraint.IntervalBoundary.OPEN), 0.3); + if(config.grab(reinsertAmountP)) { + reinsertAmount = reinsertAmountP.getValue(); + } + ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>> distanceP = new ObjectParameter<SpatialPrimitiveDoubleDistanceFunction<?>>(REINSERT_DISTANCE_ID, SpatialPrimitiveDoubleDistanceFunction.class, SquaredEuclideanDistanceFunction.class); + if(config.grab(distanceP)) { + distanceFunction = distanceP.instantiateClass(config); + } + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java new file mode 100644 index 00000000..12a4ed0f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java @@ -0,0 +1,88 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert; + +import java.util.Arrays; +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.utilities.datastructures.arraylike.ArrayAdapter; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + 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/>. + */ + +/** + * Reinsert objects on page overflow, starting with close objects first (even + * when they will likely be inserted into the same page again!) + * + * The strategy preferred by the R*-Tree + * + * @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") +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) { + 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)); + for(int i = 0; i < order.length; i++) { + double distance = distanceFunction.doubleMinDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); + order[i] = new DoubleIntPair(distance, i); + } + Arrays.sort(order, Collections.reverseOrder()); + + int num = (int) (reinsertAmount * order.length); + int[] re = new int[num]; + for(int i = 0; i < num; i++) { + re[i] = order[num - 1 - i].second; + } + return re; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractPartialReinsert.Parameterizer { + @Override + protected Object makeInstance() { + return new CloseReinsert(reinsertAmount, distanceFunction); + } + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..771f56fb --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java @@ -0,0 +1,88 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert; + +import java.util.Arrays; +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.utilities.datastructures.arraylike.ArrayAdapter; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleIntPair; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + 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/>. + */ + +/** + * Reinsert objects on page overflow, starting with farther objects first (even + * when they will likely be inserted into the same page again!) + * + * Alternative strategy mentioned in the R*-tree + * + * @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") +public class FarReinsert extends AbstractPartialReinsert { + /** + * Constructor. + * + * @param reinsertAmount Amount to reinsert + * @param distanceFunction Distance function + */ + public FarReinsert(double reinsertAmount, SpatialPrimitiveDoubleDistanceFunction<?> 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)); + for(int i = 0; i < order.length; i++) { + double distance = distanceFunction.doubleMinDist(new DoubleVector(SpatialUtil.centroid(getter.get(entries, i))), centroid); + order[i] = new DoubleIntPair(distance, i); + } + Arrays.sort(order, Collections.reverseOrder()); + + int num = (int) (reinsertAmount * order.length); + int[] re = new int[num]; + for(int i = 0; i < num; i++) { + re[i] = order[i].second; + } + return re; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractPartialReinsert.Parameterizer { + @Override + protected Object makeInstance() { + return new CloseReinsert(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 new file mode 100644 index 00000000..cba96367 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/ReinsertStrategy.java @@ -0,0 +1,44 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + 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.utilities.datastructures.arraylike.ArrayAdapter; + +/** + * Reinsertion strategy to resolve overflows in the RStarTree. + * + * @author Erich Schubert + */ +public interface ReinsertStrategy { + /** + * Perform reinsertions. + * + * @param entries Entries in overflowing node + * @param getter Adapter for the entries array + * @param page Spatial extend of the page + * @return index of pages to reinsert. + */ + public <A> int[] computeReinserts(A entries, ArrayAdapter<? extends SpatialComparable, ? super A> getter, SpatialComparable page); +} 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 new file mode 100644 index 00000000..f6a6f6e9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>Reinsertion strategies for R-Trees</p> + */ +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert;
\ No newline at end of file |