Package elki.index.tree.spatial.rstarvariants.strategies.bulk

Class SortTileRecursiveBulkSplit

java.lang.Object

elki.index.tree.spatial.rstarvariants.strategies.bulk.AbstractBulkSplit

elki.index.tree.spatial.rstarvariants.strategies.bulk.SortTileRecursiveBulkSplit

All Implemented Interfaces:

BulkSplit

@Reference(authors="S. T. Leutenegger, M. A. Lopez, J. Edgington",
           title="STR: A simple and efficient algorithm for R-tree packing",
           booktitle="Proc. 13th International Conference on Data Engineering (ICDE 1997)",
           url="https://doi.org/10.1109/ICDE.1997.582015",
           bibkey="DBLP:conf/icde/LeuteneggerEL97")
@Alias({"str","STR"})
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:

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

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SortTileRecursiveBulkSplit.Par	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
static SortTileRecursiveBulkSplit	STATIC	Static instance.

Constructor Summary

Constructors

Constructor	Description
SortTileRecursiveBulkSplit()

Method Summary

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

Methods inherited from class 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

Field Detail

STATIC

public static final SortTileRecursiveBulkSplit STATIC

Static instance.

Constructor Detail

SortTileRecursiveBulkSplit

public SortTileRecursiveBulkSplit()

Method Detail

partition

public <T extends SpatialComparable> java.util.List<java.util.List<T>> partition(java.util.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(java.util.List<T> objs,
                                                          int start,
                                                          int end,
                                                          int depth,
                                                          int dims,
                                                          int maxEntries,
                                                          SpatialSingleMeanComparator c,
                                                          java.util.List<java.util.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