io.druid.collections.spatial.split

Class GutmanSplitStrategy

java.lang.Object

io.druid.collections.spatial.split.GutmanSplitStrategy

All Implemented Interfaces:

SplitStrategy

Direct Known Subclasses:

LinearGutmanSplitStrategy, QuadraticGutmanSplitStrategy

public abstract class GutmanSplitStrategy
extends Object
implements SplitStrategy

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	GutmanSplitStrategy(int minNumChildren, int maxNumChildren, BitmapFactory b)

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Detail

GutmanSplitStrategy

protected GutmanSplitStrategy(int minNumChildren,
                              int maxNumChildren,
                              BitmapFactory b)

Method Detail

needToSplit

public boolean needToSplit(Node node)

Specified by:

needToSplit in interface SplitStrategy

split

public Node[] split(Node node)

This algorithm is from the original paper. Algorithm Split. Divide a set of M+1 index entries into two groups. S1. [Pick first entry for each group]. Apply Algorithm pickSeeds(java.util.List) to choose two entries to be the first elements of the groups. Assign each to a group. S2. [Check if done]. If all entries have been assigned, stop. If one group has so few entries that all the rest must be assigned to it in order for it to have the minimum number m, assign them and stop. S3. [Select entry to assign]. Invoke Algorithm pickNext(java.util.List, Node[]) to choose the next entry to assign. Add it to the group whose covering rectangle will have to be enlarged least to accommodate it. Resolve ties by adding the entry to the group smaller area, then to the one with fewer entries, then to either. Repeat from S2.

Specified by:

split in interface SplitStrategy

pickSeeds

public abstract Node[] pickSeeds(List<Node> nodes)

pickNext

public abstract Node pickNext(List<Node> nodes,
                              Node[] groups)