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
All Methods Instance Methods Concrete Methods 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.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 interfacePrioritySearcher<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 interfaceDBIDIter
- Specified by:
advance
in interfaceIter
- Specified by:
advance
in interfacePrioritySearcher<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.
-
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 interfacePrioritySearcher<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 interfacePrioritySearcher<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 interfacePrioritySearcher<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 interfaceDBIDRef
- 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 interfacePrioritySearcher<O extends NumberVector>
- Parameters:
threshold
- Threshold parameter- Returns:
- this, for chaining
-
-