Class BKDRadixSelector


  • public final class BKDRadixSelector
    extends java.lang.Object
    Offline Radix selector for BKD tree.
    • Field Detail

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

        private final java.lang.String tempFileNamePrefix
    • Constructor Detail

      • BKDRadixSelector

        public BKDRadixSelector​(BKDConfig config,
                                int maxPointsSortInHeap,
                                Directory tempDir,
                                java.lang.String tempFileNamePrefix)
        Sole constructor.
    • 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 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:
        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
      • getPointWriter

        PointWriter getPointWriter​(long count,
                                   java.lang.String desc)
                            throws java.io.IOException
        Throws:
        java.io.IOException