Class SimplifiedCoverTree.CoverTreePrioritySearcher<Q>
- java.lang.Object
-
- elki.index.tree.metrical.covertree.SimplifiedCoverTree.CoverTreePrioritySearcher<Q>
-
- Type Parameters:
Q
- query type
- All Implemented Interfaces:
DBIDIter
,DBIDRef
,KNNSearcher<Q>
,PrioritySearcher<Q>
,RangeSearcher<Q>
,Iter
- Direct Known Subclasses:
SimplifiedCoverTree.CoverTreePriorityDBIDSearcher
,SimplifiedCoverTree.CoverTreePriorityObjectSearcher
- Enclosing class:
- SimplifiedCoverTree<O>
public abstract class SimplifiedCoverTree.CoverTreePrioritySearcher<Q> extends java.lang.Object implements PrioritySearcher<Q>
Priority query class.- Author:
- Erich Schubert
-
-
Field Summary
Fields Modifier and Type Field Description private DBIDArrayIter
candidates
Candidatesprivate double
lb
Current lower bound.private double
maxDist
Maximum distance of current node.private DoubleObjectMinHeap<SimplifiedCoverTree.Node>
pq
Priority queueprivate double
routingDist
Distance to routing object.(package private) double
threshold
Stopping distance threshold.private DBIDVar
tmp
Temporary storage.
-
Constructor Summary
Constructors Constructor Description CoverTreePrioritySearcher()
Constructor.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description PrioritySearcher<Q>
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.PrioritySearcher<Q>
decreaseCutoff(double threshold)
Decrease the cutoff threshold.protected PrioritySearcher<Q>
doSearch()
Start the search.double
getApproximateAccuracy()
Get approximate distance accuracy (if available).double
getApproximateDistance()
Get approximate distance (if available).double
getLowerBound()
Get the lower bound (if available).double
getUpperBound()
Get the upper bound (if available).int
internalGetIndex()
Internal only: Get the internal index.protected abstract double
queryDistance(DBIDRef it)
Compute distance to query 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
getKNN, getRange, search, search
-
Methods inherited from interface elki.database.query.range.RangeSearcher
getRange
-
-
-
-
Field Detail
-
threshold
double threshold
Stopping distance threshold.
-
tmp
private DBIDVar tmp
Temporary storage.
-
pq
private DoubleObjectMinHeap<SimplifiedCoverTree.Node> pq
Priority queue
-
candidates
private DBIDArrayIter candidates
Candidates
-
routingDist
private double routingDist
Distance to routing object.
-
maxDist
private double maxDist
Maximum distance of current node.
-
lb
private double lb
Current lower bound.
-
-
Method Detail
-
queryDistance
protected abstract double queryDistance(DBIDRef it)
Compute distance to query object.- Parameters:
it
- Candidate- Returns:
- Distance
-
doSearch
protected PrioritySearcher<Q> doSearch()
Start the search.- Returns:
- this.
-
decreaseCutoff
public PrioritySearcher<Q> 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<Q>
- Parameters:
threshold
- Threshold parameter- Returns:
- this, for chaining
-
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<Q>
- Returns:
- lower bound;
0
if no guarantees (e.g., linear scan)
-
valid
public boolean valid()
Description copied from interface:Iter
Returns true if the iterator currently points to a valid object.
-
advance
public PrioritySearcher<Q> advance()
Description copied from interface:Iter
Moves the iterator forward to the next entry.
-
advanceQueue
protected boolean advanceQueue()
Expand the next node of the priority heap.
-
getApproximateDistance
public double getApproximateDistance()
Description copied from interface:PrioritySearcher
Get approximate distance (if available).Quality guarantees may vary a lot!
- Specified by:
getApproximateDistance
in interfacePrioritySearcher<Q>
- Returns:
Double.NaN
if not valid
-
getApproximateAccuracy
public double getApproximateAccuracy()
Description copied from interface:PrioritySearcher
Get approximate distance accuracy (if available).Quality guarantees may vary a lot!
- Specified by:
getApproximateAccuracy
in interfacePrioritySearcher<Q>
- Returns:
Double.NaN
if not 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 interfacePrioritySearcher<Q>
- Returns:
Double.NaN
if not valid
-
getUpperBound
public double getUpperBound()
Description copied from interface:PrioritySearcher
Get the upper bound (if available).- Specified by:
getUpperBound
in interfacePrioritySearcher<Q>
- Returns:
Double.NaN
if not valid
-
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<Q>
- 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
-
-