Package org.apache.lucene.util.bkd
Class BKDRadixSelector
- java.lang.Object
-
- org.apache.lucene.util.bkd.BKDRadixSelector
-
public final class BKDRadixSelector extends java.lang.Object
Offline Radix selector for BKD tree.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
BKDRadixSelector.PathSlice
Sliced reference to points in an PointWriter.
-
Field Summary
Fields Modifier and Type Field Description private int
bytesSorted
private BKDConfig
config
private long[]
histogram
private static int
HISTOGRAM_SIZE
private static int
MAX_SIZE_OFFLINE_BUFFER
private int
maxPointsSortInHeap
private byte[]
offlineBuffer
private int[]
partitionBucket
private byte[]
scratch
private Directory
tempDir
private java.lang.String
tempFileNamePrefix
-
Constructor Summary
Constructors Constructor Description BKDRadixSelector(BKDConfig config, int maxPointsSortInHeap, Directory tempDir, java.lang.String tempFileNamePrefix)
Sole constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private byte[]
buildHistogramAndPartition(OfflinePointWriter points, PointWriter left, PointWriter right, long from, long to, long partitionPoint, int iteration, int baseCommonPrefix, int dim)
(package private) void
checkArgs(long from, long to, long partitionPoint)
private int
findCommonPrefixAndHistogram(OfflinePointWriter points, long from, long to, int dim, int dimCommonPrefix)
private int
getBucket(int offset, int commonPrefixPosition, PointValue pointValue)
private PointWriter
getDeltaPointWriter(PointWriter left, PointWriter right, long delta, int iteration)
private int
getMaxPointsSortInHeap(PointWriter left, PointWriter right)
(package private) PointWriter
getPointWriter(long count, java.lang.String desc)
private byte[]
heapPartition(HeapPointWriter points, PointWriter left, PointWriter right, int dim, int from, int to, int partitionPoint, int commonPrefix)
private byte[]
heapRadixSelect(HeapPointWriter points, int dim, int from, int to, int partitionPoint, int commonPrefixLength)
void
heapRadixSort(HeapPointWriter points, int from, int to, int dim, int commonPrefixLength)
Sort the heap writer by the specified dim.private void
offlinePartition(OfflinePointWriter points, PointWriter left, PointWriter right, PointWriter deltaPoints, long from, long to, int dim, int bytePosition, long numDocsTiebreak)
private byte[]
partitionPointFromCommonPrefix()
byte[]
select(BKDRadixSelector.PathSlice points, BKDRadixSelector.PathSlice[] partitionSlices, long from, long to, long partitionPoint, int dim, int dimCommonPrefix)
It uses the providedpoints
from the givenfrom
to the givento
to populate thepartitionSlices
array holder (length > 1) with two path slices so the path slice at position 0 containspartition - from
points where the value of thedim
is lower or equal to theto -from
points on the slice at position 1.
-
-
-
Field Detail
-
HISTOGRAM_SIZE
private static final int HISTOGRAM_SIZE
- See Also:
- Constant Field Values
-
MAX_SIZE_OFFLINE_BUFFER
private static final int MAX_SIZE_OFFLINE_BUFFER
- See Also:
- Constant Field Values
-
histogram
private final long[] histogram
-
bytesSorted
private final int bytesSorted
-
maxPointsSortInHeap
private final int maxPointsSortInHeap
-
offlineBuffer
private final byte[] offlineBuffer
-
partitionBucket
private final int[] partitionBucket
-
scratch
private final byte[] scratch
-
tempDir
private final Directory tempDir
-
tempFileNamePrefix
private final java.lang.String tempFileNamePrefix
-
config
private final BKDConfig config
-
-
Method Detail
-
select
public byte[] select(BKDRadixSelector.PathSlice points, BKDRadixSelector.PathSlice[] partitionSlices, long from, long to, long partitionPoint, int dim, int dimCommonPrefix) throws java.io.IOException
It uses the providedpoints
from the givenfrom
to the givento
to populate thepartitionSlices
array holder (length > 1) with two path slices so the path slice at position 0 containspartition - from
points where the value of thedim
is lower or equal to theto -from
points on the slice at position 1.The
dimCommonPrefix
provides a hint for the length of the common prefix length for thedim
where are partitioning the points.It return the value of the
dim
at the partition point.If the provided
points
is wrapping anOfflinePointWriter
, the writer is destroyed in the process to save disk space.- Throws:
java.io.IOException
-
checkArgs
void checkArgs(long from, long to, long partitionPoint)
-
findCommonPrefixAndHistogram
private int findCommonPrefixAndHistogram(OfflinePointWriter points, long from, long to, int dim, int dimCommonPrefix) throws java.io.IOException
- Throws:
java.io.IOException
-
getBucket
private int getBucket(int offset, int commonPrefixPosition, PointValue pointValue)
-
buildHistogramAndPartition
private byte[] buildHistogramAndPartition(OfflinePointWriter points, PointWriter left, PointWriter right, long from, long to, long partitionPoint, int iteration, int baseCommonPrefix, int dim) throws java.io.IOException
- Throws:
java.io.IOException
-
offlinePartition
private void offlinePartition(OfflinePointWriter points, PointWriter left, PointWriter right, PointWriter deltaPoints, long from, long to, int dim, int bytePosition, long numDocsTiebreak) throws java.io.IOException
- Throws:
java.io.IOException
-
partitionPointFromCommonPrefix
private byte[] partitionPointFromCommonPrefix()
-
heapPartition
private byte[] heapPartition(HeapPointWriter points, PointWriter left, PointWriter right, int dim, int from, int to, int partitionPoint, int commonPrefix) throws java.io.IOException
- Throws:
java.io.IOException
-
heapRadixSelect
private byte[] heapRadixSelect(HeapPointWriter points, int dim, int from, int to, int partitionPoint, int commonPrefixLength)
-
heapRadixSort
public void heapRadixSort(HeapPointWriter points, int from, int to, int dim, int commonPrefixLength)
Sort the heap writer by the specified dim. It is used to sort the leaves of the tree
-
getDeltaPointWriter
private PointWriter getDeltaPointWriter(PointWriter left, PointWriter right, long delta, int iteration) throws java.io.IOException
- Throws:
java.io.IOException
-
getMaxPointsSortInHeap
private int getMaxPointsSortInHeap(PointWriter left, PointWriter right)
-
getPointWriter
PointWriter getPointWriter(long count, java.lang.String desc) throws java.io.IOException
- Throws:
java.io.IOException
-
-