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

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

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

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