Package elki.math.spacefillingcurves
Class BinarySplitSpatialSorter
- java.lang.Object
-
- 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 Description static class
BinarySplitSpatialSorter.Par
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 Description static BinarySplitSpatialSorter
STATIC
Static instance.
-
Constructor Summary
Constructors Constructor Description BinarySplitSpatialSorter()
Constructor, useSTATIC
instead!
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 elki.math.spacefillingcurves.SpatialSorter
sort
-
-
-
-
Field Detail
-
STATIC
public static final BinarySplitSpatialSorter STATIC
Static instance.
-
-
Constructor Detail
-
BinarySplitSpatialSorter
public BinarySplitSpatialSorter()
Constructor, useSTATIC
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 interfaceSpatialSorter
- Parameters:
objs
- the spatial objects to be sortedstart
- First index to sort (e.g., 0)end
- End of range (e.g.,site()
)minmax
- Array with dim pairs of (min, max) of value rangesdims
- Dimensions to sort by, for indexing vectors andminmax
.
-
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 objectsstart
- Interval startend
- Interval end (exclusive)depth
- Recursion depthnumdim
- Number of dimensionsdims
- Dimension indexes to sort by.comp
- Comparator to use
-
-