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

Class BinarySplitSpatialSorter

java.lang.Object

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 18(9)",
           url="https://doi.org/10.1145/361002.361007",
           bibkey="DBLP:journals/cacm/Bentley75")
public class BinarySplitSpatialSorter
extends java.lang.Object
implements SpatialSorter

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 18(9)

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BinarySplitSpatialSorter.Parameterizer Parameterization class.
private static class	BinarySplitSpatialSorter.Sorter Comparator for sorting spatial objects by the mean value in a single dimension.

Field Summary

Fields

Modifier and Type	Field and Description
static BinarySplitSpatialSorter	STATIC Static instance.

Constructor Summary

Constructors

Constructor and Description
BinarySplitSpatialSorter() Constructor, use STATIC instead!

Method Summary

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

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.math.spacefillingcurves.SpatialSorter

computeMinMax, sort

Field Detail

STATIC

public static final BinarySplitSpatialSorter STATIC

Static instance.

Constructor Detail

BinarySplitSpatialSorter

public BinarySplitSpatialSorter()

Constructor, use STATIC instead!

Method Detail

sort

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

Description copied from interface: SpatialSorter

Sort part of the list (start to end).

Specified by:

sort in interface SpatialSorter

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 void binarySplitSort(java.util.List<? extends SpatialComparable> objs,
                             int start,
                             int end,
                             int depth,
                             int numdim,
                             int[] dims,
                             BinarySplitSpatialSorter.Sorter comp)

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

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