io.druid.collections.spatial.split

Class LinearGutmanSplitStrategy

java.lang.Object

io.druid.collections.spatial.split.GutmanSplitStrategy

io.druid.collections.spatial.split.LinearGutmanSplitStrategy

All Implemented Interfaces:

SplitStrategy

public class LinearGutmanSplitStrategy
extends GutmanSplitStrategy

Constructor Summary

Constructors

Constructor and Description
LinearGutmanSplitStrategy(int minNumChildren, int maxNumChildren, BitmapFactory bf)

Method Summary

Modifier and Type	Method and Description
Node	pickNext(List<Node> nodes, Node[] groups) This algorithm is from the original paper.
Node[]	pickSeeds(List<Node> nodes) This algorithm is from the original paper.

Methods inherited from class io.druid.collections.spatial.split.GutmanSplitStrategy

needToSplit, split

Methods inherited from class java.lang.Object

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

Constructor Detail

LinearGutmanSplitStrategy

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

Method Detail

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,
                     Node[] groups)

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

groups - - the left and right groups

Returns:

- the optimal selected node