diff options
author | Erich Schubert <erich@debian.org> | 2012-06-02 17:47:03 +0200 |
---|---|---|
committer | Andrej Shadura <andrewsh@debian.org> | 2019-03-09 22:30:32 +0000 |
commit | 593eae6c91717eb9f4ff5088ba460dd4210509c0 (patch) | |
tree | d97e8cefb48773a382542e9e9d4a6796202a044a /src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java | |
parent | e580e42664ca92fbf8792bc39b8d59383db829fe (diff) | |
parent | c36aa2a8fd31ca5e225ff30278e910070cd2c8c1 (diff) |
Import Debian changes 0.5.0~beta2-1
elki (0.5.0~beta2-1) unstable; urgency=low
* New upstream beta release.
* Needs GNU Trove 3, in NEW.
* Build with OpenJDK7, as OpenJDK6 complains.
elki (0.5.0~beta1-1) unstable; urgency=low
* New upstream beta release.
* Needs GNU Trove 3, not yet in Debian (private package)
* Build with OpenJDK7, as OpenJDK6 complains.
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java')
-rw-r--r-- | src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/CloseReinsert.java | 88 |
1 files changed, 88 insertions, 0 deletions
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 |