de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk

Class SortTileRecursiveBulkSplit

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.AbstractBulkSplit

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.SortTileRecursiveBulkSplit

All Implemented Interfaces:

BulkSplit, InspectionUtilFrequentlyScanned, Parameterizable

@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

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:

Leutenegger, S.T. and Lopez, M.A. and Edgington, J.:
STR: A simple and efficient algorithm for R-tree packing
In: Proc. 13th International Conference on Data Engineering, 1997

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	SortTileRecursiveBulkSplit.Compare<T extends SpatialComparable> Comparison helper.

Constructor Summary

Constructors

Constructor and Description
SortTileRecursiveBulkSplit()

Method Summary

Methods

Modifier and Type	Method and Description
<T extends SpatialComparable> List<List<T>>	partition(List<T> spatialObjects, int minEntries, int maxEntries) Partitions the specified feature vectors
protected <T extends SpatialComparable> void	strPartition(List<T> objs, int start, int end, int depth, int dims, int maxEntries, SortTileRecursiveBulkSplit.Compare<T> c, List<List<T>> ret) Recursively partition.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.AbstractBulkSplit

chooseBulkSplitPoint, trivialPartition

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SortTileRecursiveBulkSplit

public SortTileRecursiveBulkSplit()

Method Detail

partition

public <T extends SpatialComparable> List<List<T>> partition(List<T> spatialObjects,
                                                    int minEntries,
                                                    int maxEntries)

Description copied from interface: BulkSplit

Partitions the specified feature vectors

Type Parameters:

T - actual type we split

Parameters:

spatialObjects - the spatial objects to be partitioned

minEntries - the minimum number of entries in a partition

maxEntries - the maximum number of entries in a partition

Returns:

the partition of the specified spatial objects

strPartition

protected <T extends SpatialComparable> void strPartition(List<T> objs,
                                              int start,
                                              int end,
                                              int depth,
                                              int dims,
                                              int maxEntries,
                                              SortTileRecursiveBulkSplit.Compare<T> c,
                                              List<List<T>> ret)

Recursively partition.

Type Parameters:

T - data type

Parameters:

objs - Object list

start - Subinterval start

end - Subinterval end

depth - Iteration depth (must be less than dimensionality!)

dims - Total number of dimensions

maxEntries - Maximum page size

c - Comparison helper

ret - Output list