de.lmu.ifi.dbs.elki.math.spacefillingcurves

Class BinarySplitSpatialSorter

java.lang.Object

de.lmu.ifi.dbs.elki.math.spacefillingcurves.AbstractSpatialSorter

de.lmu.ifi.dbs.elki.math.spacefillingcurves.BinarySplitSpatialSorter

All Implemented Interfaces:

SpatialSorter

@Reference(authors="J. L. Bentley",
           title="Multidimensional binary search trees used for associative searching",
           booktitle="Communications of the ACM, Vol. 18 Issue 9, Sept. 1975",
           url="http://dx.doi.org/10.1145/361002.361007")
public class BinarySplitSpatialSorter
extends AbstractSpatialSorter

Spatially sort the data set by repetitive binary splitting, circulating through the dimensions. This is essentially the bulk-loading proposed for the k-d-tree, as it will produce a perfectly balanced k-d-tree. The resulting order is the sequence in which objects would then be stored in the k-d-tree. Note that when using this for bulk-loading an R-tree, the result will not be a k-d-tree, not even remotely similar, as the splits are not preserved. Reference (for the bulk-loading):

J. L. Bentley
Multidimensional binary search trees used for associative searching
Communications of the ACM, Vol. 18 Issue 9, Sept. 1975

Author:

Erich Schubert

Constructor Summary

Constructors

Constructor and Description
BinarySplitSpatialSorter() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private <T extends SpatialComparable> void	binarySplitSort(List<T> objs, int start, int end, int depth, int numdim, int[] dims, SpatialSingleMeanComparator comp) Sort the array using a binary split in dimension curdim, then recurse with the next dimension.
<T extends SpatialComparable> void	sort(List<T> objs, int start, int end, double[] minmax, int[] dims) Sort part of the list (start to end).

Methods inherited from class de.lmu.ifi.dbs.elki.math.spacefillingcurves.AbstractSpatialSorter

computeMinMax, pivotizeList1D, sort

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySplitSpatialSorter

public BinarySplitSpatialSorter()

Constructor.

Method Detail

sort

public <T extends SpatialComparable> void sort(List<T> objs,
                                      int start,
                                      int end,
                                      double[] minmax,
                                      int[] dims)

Description copied from interface: SpatialSorter

Sort part of the list (start to end).

Type Parameters:

T - actual type we sort

Parameters:

objs - the spatial objects to be sorted

start - First index to sort (e.g. 0)

end - End of range (e.g. site())

minmax - Array with dim pairs of (min, max) of value ranges

dims - Dimensions to sort by, for indexing vectors and minmax.

binarySplitSort

private <T extends SpatialComparable> void binarySplitSort(List<T> objs,
                                                 int start,
                                                 int end,
                                                 int depth,
                                                 int numdim,
                                                 int[] dims,
                                                 SpatialSingleMeanComparator comp)

Sort the array using a binary split in dimension curdim, then recurse with the next dimension.

Type Parameters:

T - Object type

Parameters:

objs - List of objects

start - Interval start

end - Interval end (exclusive)

depth - Recursion depth

numdim - Number of dimensions

dims - Dimension indexes to sort by.

comp - Comparator to use