Class BKDRadixSelector

java.lang.Object
org.apache.lucene.util.bkd.BKDRadixSelector

public final class BKDRadixSelector extends Object
Offline Radix selector for BKD tree.
  • 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

      private final Directory tempDir
    • tempFileNamePrefix

      private final String tempFileNamePrefix
    • config

      private final BKDConfig config
  • Constructor Details

    • BKDRadixSelector

      public BKDRadixSelector(BKDConfig config, int maxPointsSortInHeap, Directory tempDir, String tempFileNamePrefix)
      Sole constructor.
  • 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 provided points from the given from to the given to to populate the partitionSlices array holder (length > 1) with two path slices so the path slice at position 0 contains partition - from points where the value of the dim is lower or equal to the to -from points on the slice at position 1.

      The dimCommonPrefix provides a hint for the length of the common prefix length for the dim where are partitioning the points.

      It return the value of the dim at the partition point.

      If the provided points is wrapping an OfflinePointWriter, 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

      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 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

      private int getMaxPointsSortInHeap(PointWriter left, PointWriter right)
    • getPointWriter

      PointWriter getPointWriter(long count, String desc) throws IOException
      Throws:
      IOException