de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split

Class GreeneSplit

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.GreeneSplit

All Implemented Interfaces:

SplitStrategy

@Reference(authors="D, Greene",
           title="An implementation and performance analysis of spatial data access methods",
           booktitle="Proceedings of the Fifth International Conference on Data Engineering",
           url="https://doi.org/10.1109/ICDE.1989.47268",
           bibkey="DBLP:conf/icde/Greene89")
public class GreeneSplit
extends java.lang.Object
implements SplitStrategy

Quadratic-time complexity split as used by Diane Greene for the R-Tree.

Seed selection is quadratic, distribution is O(n log n).

This contains a slight modification to improve performance with point data: with points as seeds, the normalized separation is always 1, so we choose the raw separation then.

D. Greene
An implementation and performance analysis of spatial data access methods
Proceedings of the Fifth International Conference on Data Engineering

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GreeneSplit.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static GreeneSplit	STATIC Static instance.

Constructor Summary

Constructors

Constructor and Description
GreeneSplit()

Method Summary

Modifier and Type	Method and Description
<E extends SpatialComparable,A> long[]	split(A entries, ArrayAdapter<E,A> getter, int minEntries) Split a page

Methods inherited from class java.lang.Object

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

Field Detail

STATIC

public static final GreeneSplit STATIC

Static instance.

Constructor Detail

GreeneSplit

public GreeneSplit()

Method Detail

split

public <E extends SpatialComparable,A> long[] split(A entries,
                                                    ArrayAdapter<E,A> getter,
                                                    int minEntries)

Description copied from interface: SplitStrategy

Split a page

Specified by:

split in interface SplitStrategy

Parameters:

entries - Entries to split

getter - Adapter for the entries array

minEntries - Minimum number of entries in each part

Returns:

BitSet containing the assignment.