1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
package de.lmu.ifi.dbs.elki.math.spacefillingcurves;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2013
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
import java.util.List;
import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable;
import de.lmu.ifi.dbs.elki.data.spatial.SpatialSingleMeanComparator;
import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect;
import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
/**
* 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
* <em>not</em> be a k-d-tree, not even remotely similar, as the splits are not
* preserved.
*
* Reference (for the bulk-loading):
* <p>
* J. L. Bentley<br/>
* Multidimensional binary search trees used for associative searching<br/>
* Communications of the ACM, Vol. 18 Issue 9, Sept. 1975
* </p>
*
* @author Erich Schubert
*/
@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 {
/**
* Constructor.
*/
public BinarySplitSpatialSorter() {
super();
}
@Override
public <T extends SpatialComparable> void sort(List<T> objs, int start, int end, double[] minmax, int[] dims) {
final int numdim = (dims != null) ? dims.length : (minmax.length >>> 1);
binarySplitSort(objs, start, end, 0, numdim, dims, new SpatialSingleMeanComparator(0));
}
/**
* Sort the array using a binary split in dimension curdim, then recurse with
* the next dimension.
*
* @param objs List of objects
* @param start Interval start
* @param end Interval end (exclusive)
* @param depth Recursion depth
* @param numdim Number of dimensions
* @param dims Dimension indexes to sort by.
* @param comp Comparator to use
* @param <T> Object type
*/
private <T extends SpatialComparable> void binarySplitSort(List<T> objs, final int start, final int end, int depth, final int numdim, int[] dims, SpatialSingleMeanComparator comp) {
final int mid = start + ((end - start) >>> 1);
// Make invariant
comp.setDimension(dims != null ? dims[depth] : depth);
QuickSelect.quickSelect(objs, comp, start, end, mid);
// Recurse
final int nextdim = (depth + 1) % numdim;
if (start < mid - 1) {
binarySplitSort(objs, start, mid, nextdim, numdim, dims, comp);
}
if (mid + 2 < end) {
binarySplitSort(objs, mid + 1, end, nextdim, numdim, dims, comp);
}
}
}
|