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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	BinarySplitSpatialSorter.DimC Comparator that uses only a particular dimension.

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 curdim, int dims, BinarySplitSpatialSorter.DimC 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) 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)

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

binarySplitSort

private <T extends SpatialComparable> void binarySplitSort(List<T> objs,
                                                 int start,
                                                 int end,
                                                 int curdim,
                                                 int dims,
                                                 BinarySplitSpatialSorter.DimC 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)

curdim - Current dimension

dims - Number of dimensions

comp - Comparator to use