Package elki.index.tree.spatial.rstarvariants.query

Class RStarTreeDistancePrioritySearcher<O extends SpatialComparable>

java.lang.Object

elki.index.tree.spatial.rstarvariants.query.RStarTreeDistancePrioritySearcher<O>

All Implemented Interfaces:

DBIDIter, DBIDRef, KNNSearcher<O>, PrioritySearcher<O>, RangeSearcher<O>, Iter

public class RStarTreeDistancePrioritySearcher<O extends SpatialComparable>
extends java.lang.Object
implements PrioritySearcher<O>

Instance of priority search for a particular spatial index.

Since:

0.8.0

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int	childnr	Candidate within node
protected SpatialPrimitiveDistance<? super O>	distance	Spatial primitive distance function.
private double	mindist	Distance to current node
(package private) AbstractRStarTreeNode<?,?>	node	Current node
(package private) DoubleIntegerMinHeap	pq	Priority queue
(package private) O	query	Query object
protected Relation<? extends O>	relation	Relation we query.
(package private) double	threshold	Stopping distance threshold
protected AbstractRStarTree<?,?,?>	tree	The index to use

Constructor Summary

Constructors

Constructor	Description
RStarTreeDistancePrioritySearcher(AbstractRStarTree<?,?,?> tree, Relation<? extends O> relation, SpatialPrimitiveDistance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
RStarTreeDistancePrioritySearcher<O>	advance()	Moves the iterator forward to the next entry.
protected boolean	advanceQueue()	Expand the next node of the priority heap.
double	allLowerBound()	Lower bound for all subsequent instances (that have been completely explored).
double	computeExactDistance()	Compute the exact distance to the current candidate.
RStarTreeDistancePrioritySearcher<O>	decreaseCutoff(double threshold)	Decrease the cutoff threshold.
KNNList	getKNN(O obj, int k)	Get the k nearest neighbors for a particular object.
double	getLowerBound()	Get the lower bound (if available).
ModifiableDoubleDBIDList	getRange(O obj, double range, ModifiableDoubleDBIDList result)	Get the neighbors for a particular id in a given query range.
int	internalGetIndex()	Internal only: Get the internal index.
RStarTreeDistancePrioritySearcher<O>	search(O query)	Start search with a new object.
boolean	valid()	Returns true if the iterator currently points to a valid object.

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.database.ids.DBIDIter

addTo

Methods inherited from interface elki.database.ids.DBIDRef

equals, hashCode

Methods inherited from interface elki.database.query.PrioritySearcher

getApproximateAccuracy, getApproximateDistance, getUpperBound, search

Methods inherited from interface elki.database.query.range.RangeSearcher

getRange

Field Detail

tree

protected final AbstractRStarTree<?,?,?> tree

The index to use

distance

protected final SpatialPrimitiveDistance<? super O extends SpatialComparable> distance

Spatial primitive distance function.

relation

protected Relation<? extends O extends SpatialComparable> relation

Relation we query.

query

O extends SpatialComparable query

Query object

threshold

double threshold

Stopping distance threshold

pq

DoubleIntegerMinHeap pq

Priority queue

node

AbstractRStarTreeNode<?,?> node

Current node

childnr

int childnr

Candidate within node

mindist

private double mindist

Distance to current node

Constructor Detail

RStarTreeDistancePrioritySearcher

public RStarTreeDistancePrioritySearcher(AbstractRStarTree<?,?,?> tree,
                                         Relation<? extends O> relation,
                                         SpatialPrimitiveDistance<? super O> distance)

Constructor.

Parameters:

tree - Index to use

relation - Data relation to query

distance - Distance function

Method Detail

getKNN

public KNNList getKNN(O obj,
                      int k)

Description copied from interface: KNNSearcher

Get the k nearest neighbors for a particular object.

Specified by:

getKNN in interface KNNSearcher<O extends SpatialComparable>

Specified by:

getKNN in interface PrioritySearcher<O extends SpatialComparable>

Parameters:

obj - query object

k - Number of neighbors requested

Returns:

neighbors

getRange

public ModifiableDoubleDBIDList getRange(O obj,
                                         double range,
                                         ModifiableDoubleDBIDList result)

Description copied from interface: RangeSearcher

Get the neighbors for a particular id in a given query range.

Specified by:

getRange in interface PrioritySearcher<O extends SpatialComparable>

Specified by:

getRange in interface RangeSearcher<O extends SpatialComparable>

Parameters:

obj - query object ID

range - Query range

result - Output data structure

Returns:

neighbors

search

public RStarTreeDistancePrioritySearcher<O> search(O query)

Description copied from interface: PrioritySearcher

Start search with a new object.

Specified by:

search in interface PrioritySearcher<O extends SpatialComparable>

Parameters:

query - Query object

Returns:

this, for chaining

decreaseCutoff

public RStarTreeDistancePrioritySearcher<O> decreaseCutoff(double threshold)

Description copied from interface: PrioritySearcher

Decrease the cutoff threshold.

The cutoff must not be increased, as the search may have pruned some results automatically.

Specified by:

decreaseCutoff in interface PrioritySearcher<O extends SpatialComparable>

Parameters:

threshold - Threshold parameter

Returns:

this, for chaining

valid

public boolean valid()

Description copied from interface: Iter

Returns true if the iterator currently points to a valid object.

Specified by:

valid in interface Iter

Returns:

a boolean value, whether the position is valid.

advance

public RStarTreeDistancePrioritySearcher<O> advance()

Description copied from interface: Iter

Moves the iterator forward to the next entry.

Specified by:

advance in interface DBIDIter

Specified by:

advance in interface Iter

Specified by:

advance in interface PrioritySearcher<O extends SpatialComparable>

Returns:

The iterator itself.

advanceQueue

protected boolean advanceQueue()

Expand the next node of the priority heap.

getLowerBound

public double getLowerBound()

Description copied from interface: PrioritySearcher

Get the lower bound (if available).

Note: the lower bound is already checked by the cutoff of the priority search, so this is primarily useful for analyzing the search behavior.

Specified by:

getLowerBound in interface PrioritySearcher<O extends SpatialComparable>

Returns:

Double.NaN if not valid

allLowerBound

public double allLowerBound()

Description copied from interface: PrioritySearcher

Lower bound for all subsequent instances (that have been completely explored). The searcher guarantees that no further results will be returned with a distance less than this.

Specified by:

allLowerBound in interface PrioritySearcher<O extends SpatialComparable>

Returns:

lower bound; 0 if no guarantees (e.g., linear scan)

computeExactDistance

public double computeExactDistance()

Description copied from interface: PrioritySearcher

Compute the exact distance to the current candidate.

The searcher may or may not have this value already.

Specified by:

computeExactDistance in interface PrioritySearcher<O extends SpatialComparable>

Returns:

Distance

internalGetIndex

public int internalGetIndex()

Description copied from interface: DBIDRef

Internal only: Get the internal index.

NOT FOR PUBLIC USE - ELKI Optimization engine only.

Specified by:

internalGetIndex in interface DBIDRef

Returns:

Internal index