org.apache.lucene.util.bkd

Class 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 8, 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.