Package org.apache.druid.collections.spatial.split

Class LinearGutmanSplitStrategy

java.lang.Object
org.apache.druid.collections.spatial.split.GutmanSplitStrategy
org.apache.druid.collections.spatial.split.LinearGutmanSplitStrategy
All Implemented Interfaces:
SplitStrategy
public class LinearGutmanSplitStrategy extends GutmanSplitStrategy

  • Constructor Details

    • LinearGutmanSplitStrategy

      public LinearGutmanSplitStrategy(int minNumChildren, int maxNumChildren, BitmapFactory bf)

  • Method Details

    • pickSeeds

      public Node[] pickSeeds(List<Node> nodes)
      This algorithm is from the original paper. Algorithm LinearPickSeeds. Select two entries to be the first elements of the groups. LPS1. [Find extreme rectangles along all dimensions]. Along each dimension, find the entry whose rectangle has the highest low side, and the one with the lowest high side. Record the separation. LPS2. [Adjust for shape of the rectangle cluster]. Normalize the separations by dividing by the width of the entire set along the corresponding dimension. LPS3. [Select the most extreme pair]. Choose the pair with the greatest normalized separation along any dimension.
      Specified by:
      pickSeeds in class GutmanSplitStrategy
      Parameters:
      nodes - - nodes to choose from
      Returns:
      - two groups representing the seeds

    • pickNext

      public Node pickNext(List<Node> nodes)
      This algorithm is from the original paper. Algorithm LinearPickNext. PickNext simply choose any of the remaining entries.
      Specified by:
      pickNext in class GutmanSplitStrategy
      Parameters:
      nodes - - remaining nodes
      Returns:
      - the optimal selected node