diff options
author | Andrej Shadura <andrewsh@debian.org> | 2019-03-09 22:30:32 +0000 |
---|---|---|
committer | Andrej Shadura <andrewsh@debian.org> | 2019-03-09 22:30:32 +0000 |
commit | c36aa2a8fd31ca5e225ff30278e910070cd2c8c1 (patch) | |
tree | bdfe1a5ccb57999d4d664a2a44121a78c88b19d4 /src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java | |
parent | 89aa1958dbaf9052da0c24706308a2ef8cefa96e (diff) |
Import Upstream version 0.5.0~beta2
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java')
-rw-r--r-- | src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/reinsert/FarReinsert.java | 88 |
1 files changed, 88 insertions, 0 deletions
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 |