diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk')
8 files changed, 708 insertions, 0 deletions
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 new file mode 100644 index 00000000..4a0304f1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/AbstractBulkSplit.java @@ -0,0 +1,91 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk; + +import java.util.ArrayList; +import java.util.List; + +/* + 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/>. + */ + +/** + * Encapsulates the required parameters for a bulk split of a spatial index. + * + * @author Elke Achtert + */ +public abstract class AbstractBulkSplit implements BulkSplit { + /** + * Constructor + */ + public AbstractBulkSplit() { + // Nothing to do + } + + /** + * Computes and returns the best split point. + * + * @param numEntries the number of entries to be split + * @param minEntries the number of minimum entries in the node to be split + * @param maxEntries number of maximum entries in the node to be split + * @return the best split point + */ + protected int chooseBulkSplitPoint(int numEntries, int minEntries, int maxEntries) { + if(numEntries < minEntries) { + throw new IllegalArgumentException("numEntries < minEntries!"); + } + + if(numEntries <= maxEntries) { + return numEntries; + } + else if(numEntries < maxEntries + minEntries) { + return (numEntries - minEntries); + } + else { + return maxEntries; + } + } + + /** + * Perform the trivial partitioning of the given list. + * + * @param objects Objects to partition + * @param minEntries Minimum number of objects per page + * @param maxEntries Maximum number of objects per page. + * @return List with partitions + */ + protected <T> List<List<T>> trivialPartition(List<T> objects, int minEntries, int maxEntries) { + // build partitions + final int size = objects.size(); + final int numberPartitions = (int) Math.ceil(((double) size) / maxEntries); + List<List<T>> partitions = new ArrayList<List<T>>(numberPartitions); + int start = 0; + for(int pnum = 0; pnum < numberPartitions; pnum++) { + int end = (int) ((pnum + 1.) * size / numberPartitions); + if(pnum == numberPartitions - 1) { + end = size; + } + assert ((end - start) >= minEntries && (end - start) <= maxEntries); + partitions.add(objects.subList(start, end)); + start = end; + } + return partitions; + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..1eb88f7c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/BulkSplit.java @@ -0,0 +1,47 @@ +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) 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 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 { + /** + * Partitions the specified feature vectors + * + * @param <T> actual type we split + * @param spatialObjects the spatial objects to be partitioned + * @param minEntries the minimum number of entries in a partition + * @param maxEntries the maximum number of entries in a partition + * @return the partition of the specified spatial objects + */ + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries); +}
\ No newline at end of file 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 new file mode 100644 index 00000000..308c70cb --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/FileOrderBulkSplit.java @@ -0,0 +1,67 @@ +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) 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 java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * Trivial bulk loading - assumes that the file has been appropriately sorted + * before. + * + * @author Erich Schubert + */ +public class FileOrderBulkSplit extends AbstractBulkSplit { + /** + * Static instance + */ + public static final FileOrderBulkSplit STATIC = new FileOrderBulkSplit(); + + /** + * Constructor. + */ + protected FileOrderBulkSplit() { + super(); + } + + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + return trivialPartition(spatialObjects, minEntries, maxEntries); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected FileOrderBulkSplit makeInstance() { + return FileOrderBulkSplit.STATIC; + } + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..90a8b622 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/MaxExtensionBulkSplit.java @@ -0,0 +1,169 @@ +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) 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 java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util.SpatialComparator; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * Split strategy for bulk-loading a spatial tree where the split axes are the + * dimensions with maximum extension. + * + * @author Elke Achtert + * + * @apiviz.uses SpatialComparator + */ +public class MaxExtensionBulkSplit extends AbstractBulkSplit { + /** + * Logger. + */ + private static final Logging logger = Logging.getLogger(MaxExtensionBulkSplit.class); + + /** + * Static instance + */ + public static final MaxExtensionBulkSplit STATIC = new MaxExtensionBulkSplit(); + + /** + * Constructor + */ + public MaxExtensionBulkSplit() { + // Nothing to do + } + + /** + * Partitions the specified feature vectors where the split axes are the + * dimensions with maximum extension. + * + * @param spatialObjects the spatial objects to be partitioned + * @param minEntries the minimum number of entries in a partition + * @param maxEntries the maximum number of entries in a partition + * @return the partition of the specified spatial objects + */ + @Override + public <N extends SpatialComparable> List<List<N>> partition(List<N> spatialObjects, int minEntries, int maxEntries) { + List<List<N>> partitions = new ArrayList<List<N>>(); + List<N> objects = new ArrayList<N>(spatialObjects); + + while(objects.size() > 0) { + StringBuffer msg = new StringBuffer(); + + // get the split axis and split point + int splitAxis = chooseMaximalExtendedSplitAxis(objects); + int splitPoint = chooseBulkSplitPoint(objects.size(), minEntries, maxEntries); + if(logger.isDebugging()) { + msg.append("\nsplitAxis ").append(splitAxis); + msg.append("\nsplitPoint ").append(splitPoint); + } + + // sort in the right dimension + Collections.sort(objects, new SpatialComparator(splitAxis, SpatialComparator.MIN)); + + // insert into partition + List<N> partition1 = new ArrayList<N>(); + for(int i = 0; i < splitPoint; i++) { + N o = objects.remove(0); + partition1.add(o); + } + partitions.add(partition1); + + // copy array + if(logger.isDebugging()) { + msg.append("\ncurrent partition " + partition1); + msg.append("\nremaining objects # ").append(objects.size()); + logger.debugFine(msg.toString()); + } + } + + if(logger.isDebugging()) { + logger.debugFine("partitions " + partitions); + } + return partitions; + } + + /** + * Computes and returns the best split axis. The best split axis is the split + * axes with the maximal extension. + * + * @param objects the spatial objects to be split + * @return the best split axis + */ + private int chooseMaximalExtendedSplitAxis(List<? extends SpatialComparable> objects) { + // maximum and minimum value for the extension + int dimension = objects.get(0).getDimensionality(); + double[] maxExtension = new double[dimension]; + double[] minExtension = new double[dimension]; + Arrays.fill(minExtension, Double.MAX_VALUE); + + // compute min and max value in each dimension + for(SpatialComparable object : objects) { + for(int d = 1; d <= dimension; d++) { + double min, max; + min = object.getMin(d); + max = object.getMax(d); + + if(maxExtension[d - 1] < max) { + maxExtension[d - 1] = max; + } + + if(minExtension[d - 1] > min) { + minExtension[d - 1] = min; + } + } + } + + // set split axis to dim with maximal extension + int splitAxis = -1; + double max = 0; + for(int d = 1; d <= dimension; d++) { + double currentExtension = maxExtension[d - 1] - minExtension[d - 1]; + if(max < currentExtension) { + max = currentExtension; + splitAxis = d; + } + } + return splitAxis; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected MaxExtensionBulkSplit makeInstance() { + return MaxExtensionBulkSplit.STATIC; + } + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..b99ae01e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/OneDimSortBulkSplit.java @@ -0,0 +1,86 @@ +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) 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 java.util.Collections; +import java.util.Comparator; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * Simple bulk loading strategy by sorting the data along the first dimension. + * + * This is also known as Nearest-X, and attributed to: + * <p> + * Roussopoulos, N. and Leifker, D.:<br /> + * Direct spatial search on pictorial databases using packed R-trees<br /> + * In: ACM SIGMOD Record 14-4 + * </p> + * + * @author Erich Schubert + */ +@Reference(authors = "Roussopoulos, N. and Leifker, D.", title = "Direct spatial search on pictorial databases using packed R-trees", booktitle = "ACM SIGMOD Record 14-4", url = "http://dx.doi.org/10.1145/971699.318900") +public class OneDimSortBulkSplit extends AbstractBulkSplit { + /** + * Static instance + */ + public static final AbstractBulkSplit STATIC = new OneDimSortBulkSplit(); + + /** + * Constructor. + */ + protected OneDimSortBulkSplit() { + super(); + } + + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + // Sort by first dimension + Collections.sort(spatialObjects, new Comparator<SpatialComparable>() { + @Override + public int compare(SpatialComparable o1, SpatialComparable o2) { + double min1 = (o1.getMax(1) + o1.getMin(1)) / 2; + double min2 = (o2.getMax(1) + o2.getMin(1)) / 2; + return Double.compare(min1, min2); + } + }); + return trivialPartition(spatialObjects, minEntries, maxEntries); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected AbstractBulkSplit makeInstance() { + return OneDimSortBulkSplit.STATIC; + } + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..28e96da6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SortTileRecursiveBulkSplit.java @@ -0,0 +1,115 @@ +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) 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 java.util.ArrayList; +import java.util.Comparator; +import java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; + +/** + * Sort-Tile-Recursive aims at tiling the data space with a grid-like structure + * for partitioning the dataset into the required number of buckets. + * + * Reference: + * <p> + * Leutenegger, S.T. and Lopez, M.A. and Edgington, J.:<br /> + * STR: A simple and efficient algorithm for R-tree packing<br /> + * In: Proc. 13th International Conference on Data Engineering, 1997 + * </p> + * + * @author Erich Schubert + */ +@Reference(authors = "Leutenegger, S.T. and Lopez, M.A. and Edgington, J.", title = "STR: A simple and efficient algorithm for R-tree packing", booktitle = "Proc. 13th International Conference on Data Engineering, 1997", url = "http://dx.doi.org/10.1109/ICDE.1997.582015") +public class SortTileRecursiveBulkSplit extends AbstractBulkSplit { + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + final int dims = spatialObjects.get(0).getDimensionality(); + final int p = (int) Math.ceil(spatialObjects.size() / (double) maxEntries); + List<List<T>> ret = new ArrayList<List<T>>(p); + strPartition(spatialObjects, 0, spatialObjects.size(), 0, dims, maxEntries, new Compare<T>(), ret); + return ret; + } + + /** + * Recursively partition. + * + * @param objs Object list + * @param start Subinterval start + * @param end Subinteval end + * @param depth Iteration depth (must be less than dimensionality!) + * @param dims Total number of dimensions + * @param maxEntries Maximum page size + * @param c Comparison helper + * @param ret Output list + */ + protected <T extends SpatialComparable> void strPartition(List<T> objs, int start, int end, int depth, int dims, int maxEntries, Compare<T> c, List<List<T>> ret) { + c.dim = depth + 1; + final int p = (int) Math.ceil((end - start) / (double) maxEntries); + final int s = (int) Math.ceil(Math.pow(p, 1.0 / (dims - depth))); + + final double len = end - start; // double intentional! + for(int i = 0; i < s; i++) { + // We don't completely sort, but only ensure the quantile is invariant. + int s2 = start + (int) ((i * len) / s); + int e2 = start + (int) (((i + 1) * len) / s); + // LoggingUtil.warning("STR " + dim + " s2:" + s2 + " e2:" + e2); + if(e2 < end) { + QuickSelect.quickSelect(objs, c, s2, end, e2); + } + if(depth + 1 == dims) { + ret.add(objs.subList(s2, e2)); + } + else { + // Descend + strPartition(objs, s2, e2, depth + 1, dims, maxEntries, c, ret); + } + } + } + + /** + * Comparison helper. + * + * @apiviz.exclude + * + * @author Erich Schubert + * + * @param <T> Type + */ + private static class Compare<T extends SpatialComparable> implements Comparator<T> { + /** + * Current dimension + */ + public int dim; + + @Override + public int compare(T o1, T o2) { + final double v1 = o1.getMin(dim) + o1.getMax(dim); + final double v2 = o2.getMin(dim) + o2.getMax(dim); + return Double.compare(v1, v2); + } + } +}
\ No newline at end of file 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 new file mode 100644 index 00000000..9c3a41a1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/SpatialSortBulkSplit.java @@ -0,0 +1,107 @@ +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) 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 java.util.List; + +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.math.spacefillingcurves.SpatialSorter; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +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.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; + +/** + * Bulk loading by spatially sorting the objects, then partitioning the sorted + * list appropriately. + * + * Based conceptually on: + * <p> + * On packing R-trees<br/> + * Kamel, I. and Faloutsos, C.<br/> + * Proc. 2of the second international conference on Information and knowledge + * management + * </p> + * + * @apiviz.composedOf SpatialSorter + * + * @author Erich Schubert + */ +@Reference(title = "On packing R-trees", authors = "Kamel, I. and Faloutsos, C.", booktitle = "Proc. 2of the second international conference on Information and knowledge management", url = "http://dx.doi.org/10.1145/170088.170403") +public class SpatialSortBulkSplit extends AbstractBulkSplit { + /** + * Sorting class + */ + final SpatialSorter sorter; + + /** + * Constructor. + * + * @param sorter Sorting strategy + */ + protected SpatialSortBulkSplit(SpatialSorter sorter) { + super(); + this.sorter = sorter; + } + + @Override + public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects, int minEntries, int maxEntries) { + sorter.sort(spatialObjects); + return super.trivialPartition(spatialObjects, minEntries, maxEntries); + } + + /** + * Parametization class + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + /** + * Option ID for spatial sorting + */ + public static final OptionID SORTER_ID = OptionID.getOrCreateOptionID("rtree.bulk.spatial-sort", "Strategy for spatial sorting in bulk loading."); + + /** + * Sorting class + */ + SpatialSorter sorter; + + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + + ObjectParameter<SpatialSorter> sorterP = new ObjectParameter<SpatialSorter>(SORTER_ID, SpatialSorter.class); + if(config.grab(sorterP)) { + sorter = sorterP.instantiateClass(config); + } + } + + @Override + protected SpatialSortBulkSplit makeInstance() { + return new SpatialSortBulkSplit(sorter); + } + } +} 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 new file mode 100644 index 00000000..0d01ba83 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/strategies/bulk/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>Packages for bulk-loading 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.bulk;
\ No newline at end of file |