java.lang.Object
org.apache.lucene.util.bkd.BKDRadixSelector
Offline Radix selector for BKD tree.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final record
Sliced reference to points in an PointWriter. -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionBKDRadixSelector
(BKDConfig config, int maxPointsSortInHeap, Directory tempDir, String tempFileNamePrefix) Sole constructor. -
Method Summary
Modifier and TypeMethodDescriptionprivate 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, 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[]
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 Details
-
HISTOGRAM_SIZE
private static final int HISTOGRAM_SIZE- See Also:
-
MAX_SIZE_OFFLINE_BUFFER
private static final int MAX_SIZE_OFFLINE_BUFFER- See Also:
-
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
-
tempFileNamePrefix
-
config
-
-
Constructor Details
-
Method Details
-
select
public byte[] select(BKDRadixSelector.PathSlice points, BKDRadixSelector.PathSlice[] partitionSlices, long from, long to, long partitionPoint, int dim, int dimCommonPrefix) throws 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:
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 IOException - Throws:
IOException
-
getBucket
-
buildHistogramAndPartition
private byte[] buildHistogramAndPartition(OfflinePointWriter points, PointWriter left, PointWriter right, long from, long to, long partitionPoint, int iteration, int baseCommonPrefix, int dim) throws IOException - Throws:
IOException
-
offlinePartition
private void offlinePartition(OfflinePointWriter points, PointWriter left, PointWriter right, PointWriter deltaPoints, long from, long to, int dim, int bytePosition, long numDocsTiebreak) throws IOException - Throws:
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 IOException - Throws:
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 IOException - Throws:
IOException
-
getMaxPointsSortInHeap
-
getPointWriter
- Throws:
IOException
-