Package elki.index.tree.spatial.kd

Class MemoryKDTree.KDTreePrioritySearcher

java.lang.Object

elki.index.tree.spatial.kd.MemoryKDTree.KDTreePrioritySearcher

All Implemented Interfaces:

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

Enclosing class:

MemoryKDTree<O extends NumberVector>

public class MemoryKDTree.KDTreePrioritySearcher
extends java.lang.Object
implements PrioritySearcher<O>

Priority search for the k-d-tree.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
private MemoryKDTree.PrioritySearchBranch	cur	Current search position.
private PartialDistance<? super O>	distance	Distance to use.
private ComparableMinHeap<MemoryKDTree.PrioritySearchBranch>	heap	Min heap for searching.
private DBIDArrayIter	iter	Search iterator.
private int	pos	Position within leaf.
private O	query	Current query object.
private double	threshold	Stopping threshold.

Constructor Summary

Constructors

Constructor	Description
KDTreePrioritySearcher(PartialDistance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
PrioritySearcher<O>	advance()	Moves the iterator forward to the next entry.
double	allLowerBound()	Lower bound for all subsequent instances (that have been completely explored).
double	computeExactDistance()	Compute the exact distance to the current candidate.
PrioritySearcher<O>	decreaseCutoff(double threshold)	Decrease the cutoff threshold.
double	getLowerBound()	Get the lower bound (if available).
int	internalGetIndex()	Internal only: Get the internal index.
PrioritySearcher<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, getKNN, getRange, getUpperBound, search

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

getRange

Field Detail

distance

private PartialDistance<? super O extends NumberVector> distance

Distance to use.

heap

private ComparableMinHeap<MemoryKDTree.PrioritySearchBranch> heap

Min heap for searching.

iter

private DBIDArrayIter iter

Search iterator.

query

private O extends NumberVector query

Current query object.

threshold

private double threshold

Stopping threshold.

pos

private int pos

Position within leaf.

cur

private MemoryKDTree.PrioritySearchBranch cur

Current search position.

Constructor Detail

KDTreePrioritySearcher

public KDTreePrioritySearcher(PartialDistance<? super O> distance)

Constructor.

Parameters:

distance - Distance to use

Method Detail

search

public PrioritySearcher<O> search(O query)

Description copied from interface: PrioritySearcher

Start search with a new object.

Specified by:

search in interface PrioritySearcher<O extends NumberVector>

Parameters:

query - Query object

Returns:

this, for chaining

advance

public PrioritySearcher<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 NumberVector>

Returns:

The iterator itself.

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.

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 NumberVector>

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 NumberVector>

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 NumberVector>

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

decreaseCutoff

public PrioritySearcher<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 NumberVector>

Parameters:

threshold - Threshold parameter

Returns:

this, for chaining