org.apache.lucene.util.bkd

Class BKDWriter

java.lang.Object

org.apache.lucene.util.bkd.BKDWriter

All Implemented Interfaces:

Closeable, AutoCloseable

public class BKDWriter
extends Object
implements Closeable

Recursively builds a block KD-tree to assign all incoming points in N-dim space to smaller and smaller N-dim rectangles (cells) until the number of points in a given rectangle is <= maxPointsInLeafNode. The tree is fully balanced, which means the leaf nodes will have between 50% and 100% of the requested maxPointsInLeafNode. Values that fall exactly on a cell boundary may be in either cell.

The number of dimensions can be 1 to 255, but every byte[] value is fixed length.

See this paper for details.

This consumes heap during writing: it allocates a LongBitSet(numPoints), and then uses up to the specified maxMBSortInHeap heap space for writing.

NOTE: This can write at most Integer.MAX_VALUE * maxPointsInLeafNode total points, and

WARNING: This API is experimental and might change in incompatible ways in the next release.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	bytesPerDim How many bytes each value in each dimension takes.
static String	CODEC_NAME
static float	DEFAULT_MAX_MB_SORT_IN_HEAP Default maximum heap to use, before spilling to (slower) disk
static int	DEFAULT_MAX_POINTS_IN_LEAF_NODE Default maximum number of point in each leaf block
protected FixedBitSet	docsSeen
static int	MAX_DIMS Maximum number of dimensions
protected byte[]	maxPackedValue Maximum per-dim values, packed
protected int	maxPointsInLeafNode
protected byte[]	minPackedValue Minimum per-dim values, packed
protected int	numDims How many dimensions we are indexing
protected int	packedBytesLength numDims * bytesPerDim
protected long	pointCount
static int	VERSION_CURRENT
static int	VERSION_START

Constructor Summary

Constructors

Constructor and Description
BKDWriter(int maxDoc, Directory tempDir, String tempFileNamePrefix, int numDims, int bytesPerDim)
BKDWriter(int maxDoc, Directory tempDir, String tempFileNamePrefix, int numDims, int bytesPerDim, int maxPointsInLeafNode, double maxMBSortInHeap)

Method Summary

Modifier and Type	Method and Description
void	add(byte[] packedValue, int docID)
void	close()
long	finish(IndexOutput out) Writes the BKD tree to the provided IndexOutput and returns the file offset where index was written.
long	getPointCount() How many points have been added so far
long	merge(IndexOutput out, List<MergeState.DocMap> docMaps, List<BKDReader> readers, List<Integer> docIDBases) More efficient bulk-add for incoming BKDReaders.
protected int	split(byte[] minPackedValue, byte[] maxPackedValue)
static void	verifyParams(int numDims, int maxPointsInLeafNode, double maxMBSortInHeap)
protected void	writeCommonPrefixes(IndexOutput out, int[] commonPrefixes, byte[] packedValue)
protected void	writeIndex(IndexOutput out, long[] leafBlockFPs, byte[] splitPackedValues) Subclass can change how it writes the index.
protected void	writeLeafBlockDocs(IndexOutput out, int[] docIDs, int start, int count)
protected void	writeLeafBlockPackedValue(IndexOutput out, int[] commonPrefixLengths, byte[] bytes)

Methods inherited from class java.lang.Object

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

Field Detail

CODEC_NAME

public static final String CODEC_NAME

See Also:

Constant Field Values

VERSION_START

public static final int VERSION_START

See Also:

Constant Field Values

VERSION_CURRENT

public static final int VERSION_CURRENT

See Also:

Constant Field Values

DEFAULT_MAX_POINTS_IN_LEAF_NODE

public static final int DEFAULT_MAX_POINTS_IN_LEAF_NODE

Default maximum number of point in each leaf block

See Also:

Constant Field Values

DEFAULT_MAX_MB_SORT_IN_HEAP

public static final float DEFAULT_MAX_MB_SORT_IN_HEAP

Default maximum heap to use, before spilling to (slower) disk

See Also:

Constant Field Values

MAX_DIMS

public static final int MAX_DIMS

Maximum number of dimensions

See Also:

Constant Field Values

numDims

protected final int numDims

How many dimensions we are indexing

bytesPerDim

protected final int bytesPerDim

How many bytes each value in each dimension takes.

packedBytesLength

protected final int packedBytesLength

numDims * bytesPerDim

docsSeen

protected final FixedBitSet docsSeen

maxPointsInLeafNode

protected final int maxPointsInLeafNode

minPackedValue

protected final byte[] minPackedValue

Minimum per-dim values, packed

maxPackedValue

protected final byte[] maxPackedValue

Maximum per-dim values, packed

pointCount

protected long pointCount

Constructor Detail

BKDWriter

public BKDWriter(int maxDoc,
                 Directory tempDir,
                 String tempFileNamePrefix,
                 int numDims,
                 int bytesPerDim)
          throws IOException

Throws:

IOException

BKDWriter

public BKDWriter(int maxDoc,
                 Directory tempDir,
                 String tempFileNamePrefix,
                 int numDims,
                 int bytesPerDim,
                 int maxPointsInLeafNode,
                 double maxMBSortInHeap)
          throws IOException

Throws:

IOException

Method Detail

verifyParams

public static void verifyParams(int numDims,
                                int maxPointsInLeafNode,
                                double maxMBSortInHeap)

add

public void add(byte[] packedValue,
                int docID)
         throws IOException

Throws:

IOException

getPointCount

public long getPointCount()

How many points have been added so far

merge

public long merge(IndexOutput out,
                  List<MergeState.DocMap> docMaps,
                  List<BKDReader> readers,
                  List<Integer> docIDBases)
           throws IOException

More efficient bulk-add for incoming BKDReaders. This does a merge sort of the already sorted values and currently only works when numDims==1. This returns -1 if all documents containing dimensional values were deleted.

Throws:

IOException

finish

public long finish(IndexOutput out)
            throws IOException

Writes the BKD tree to the provided IndexOutput and returns the file offset where index was written.

Throws:

IOException

writeIndex

protected void writeIndex(IndexOutput out,
                          long[] leafBlockFPs,
                          byte[] splitPackedValues)
                   throws IOException

Subclass can change how it writes the index.

Throws:

IOException

writeLeafBlockDocs

protected void writeLeafBlockDocs(IndexOutput out,
                                  int[] docIDs,
                                  int start,
                                  int count)
                           throws IOException

Throws:

IOException

writeLeafBlockPackedValue

protected void writeLeafBlockPackedValue(IndexOutput out,
                                         int[] commonPrefixLengths,
                                         byte[] bytes)
                                  throws IOException

Throws:

IOException

writeCommonPrefixes

protected void writeCommonPrefixes(IndexOutput out,
                                   int[] commonPrefixes,
                                   byte[] packedValue)
                            throws IOException

Throws:

IOException

close

public void close()
           throws IOException

Specified by:

close in interface Closeable

Specified by:

close in interface AutoCloseable

Throws:

IOException

split

protected int split(byte[] minPackedValue,
                    byte[] maxPackedValue)