Package elki.index.tree.spatial.rstarvariants.strategies.split

Class AngTanLinearSplit

java.lang.Object

elki.index.tree.spatial.rstarvariants.strategies.split.AngTanLinearSplit

All Implemented Interfaces:

SplitStrategy

@Reference(authors="C. H. Ang, T. C. Tan",
           title="New linear node splitting algorithm for R-trees",
           booktitle="Proc. 5th Int. Sym. on Advances in Spatial Databases",
           url="https://doi.org/10.1007/3-540-63238-7_38",
           bibkey="DBLP:conf/ssd/AngT97")
public class AngTanLinearSplit
extends java.lang.Object
implements SplitStrategy

Line-time complexity split proposed by Ang and Tan.

This split strategy tries to minimize overlap only, which can however degenerate to "slices".

Reference:

C. H. Ang, T. C. Tan:
New linear node splitting algorithm for R-trees
Proc. 5th Int. Symp. on Advances in Spatial Databases

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	AngTanLinearSplit.Par	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
private static Logging	LOG	Logger class
static AngTanLinearSplit	STATIC	Static instance.

Constructor Summary

Constructors

Constructor	Description
AngTanLinearSplit()

Method Summary

Modifier and Type	Method	Description
protected <E extends SpatialComparable,A> double	computeOverlap(A entries, ArrayAdapter<E,A> getter, long[] assign)	Compute overlap of assignment
<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

LOG

private static final Logging LOG

Logger class

STATIC

public static final AngTanLinearSplit STATIC

Static instance.

Constructor Detail

AngTanLinearSplit

public AngTanLinearSplit()

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.

computeOverlap

protected <E extends SpatialComparable,A> double computeOverlap(A entries,
                                                                      ArrayAdapter<E,A> getter,
                                                                      long[] assign)

Compute overlap of assignment

Parameters:

entries - Entries

getter - Entry accessor

assign - Assignment

Returns:

Overlap amount