Package elki.database.query

Interface PrioritySearcher<O>

Type Parameters:

O - Object type

All Superinterfaces:

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

All Known Implementing Classes:

CoverTree.CoverTreePriorityDBIDSearcher, CoverTree.CoverTreePriorityObjectSearcher, CoverTree.CoverTreePrioritySearcher, EuclideanRStarTreeDistancePrioritySearcher, ExactPrioritySearcher, GNAT.GNATPriorityDBIDSearcher, GNAT.GNATPriorityObjectSearcher, GNAT.GNATPrioritySearcher, LinearScanEuclideanPrioritySearcher, LinearScanEuclideanPrioritySearcher.ByDBID, LinearScanEuclideanPrioritySearcher.ByObject, LinearScanPrioritySearcher, LinearScanPrioritySearcher.ByDBID, LinearScanPrioritySearcher.ByObject, MemoryKDTree.KDTreePrioritySearcher, MinimalisticMemoryKDTree.KDTreePrioritySearcher, PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher, RStarTreeDistancePrioritySearcher, SimplifiedCoverTree.CoverTreePriorityDBIDSearcher, SimplifiedCoverTree.CoverTreePriorityObjectSearcher, SimplifiedCoverTree.CoverTreePrioritySearcher, SmallMemoryKDTree.KDTreePrioritySearcher, VPTree.VPTreePriorityDBIDSearcher, VPTree.VPTreePriorityObjectSearcher, VPTree.VPTreePrioritySearcher, WrappedPrioritySearchDBIDByLookup, WrappedPrioritySearchDBIDByLookup.Linear

public interface PrioritySearcher<O>
extends KNNSearcher<O>, RangeSearcher<O>, DBIDIter

Distance priority-based searcher. When used with an index, this will return relevant objects in - approximately - increasing order. But unless you give the hint QueryBuilder.optimizedOnly(), the system may fall back to a slow linear scan that returns objects in arbitrary order, if no suitable index is available.

This searcher has fairly loose guarantees because it may need to fall back to a linear scan. In such cases, you may be given every point in arbitrary order. But if you set some thresholds, it may even then be able to avoid some computations, such as computing the square root in Euclidean distance.

Since:

0.8.0

Author:

Erich Schubert

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.
default double	getApproximateAccuracy()	Get approximate distance accuracy (if available).
default double	getApproximateDistance()	Get approximate distance (if available).
default KNNList	getKNN(O obj, int k)	Get the k nearest neighbors for a particular object.
default double	getLowerBound()	Get the lower bound (if available).
default ModifiableDoubleDBIDList	getRange(O obj, double range, ModifiableDoubleDBIDList result)	Get the neighbors for a particular id in a given query range.
default double	getUpperBound()	Get the upper bound (if available).
PrioritySearcher<O>	search(O query)	Start search with a new object.
default PrioritySearcher<O>	search(O query, double threshold)	Priority search function.

Methods inherited from interface elki.database.ids.DBIDIter

addTo

Methods inherited from interface elki.database.ids.DBIDRef

equals, hashCode, internalGetIndex

Methods inherited from interface elki.utilities.datastructures.iterator.Iter

valid

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

getRange

Method Detail

search

default PrioritySearcher<O> search(O query,
                                   double threshold)

Priority search function.

Parameters:

query - Query object

threshold - Initial distance threshold

Returns:

this, for chaining

search

PrioritySearcher<O> search(O query)

Start search with a new object.

Parameters:

query - Query object

Returns:

this, for chaining

getKNN

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

Parameters:

obj - query object

k - Number of neighbors requested

Returns:

neighbors

getRange

default 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 RangeSearcher<O>

Parameters:

obj - query object ID

range - Query range

result - Output data structure

Returns:

neighbors

decreaseCutoff

PrioritySearcher<O> decreaseCutoff(double threshold)

Decrease the cutoff threshold.

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

Parameters:

threshold - Threshold parameter

Returns:

this, for chaining

computeExactDistance

double computeExactDistance()

Compute the exact distance to the current candidate.

The searcher may or may not have this value already.

Returns:

Distance

getApproximateDistance

default double getApproximateDistance()

Get approximate distance (if available).

Quality guarantees may vary a lot!

Returns:

Double.NaN if not valid

getApproximateAccuracy

default double getApproximateAccuracy()

Get approximate distance accuracy (if available).

Quality guarantees may vary a lot!

Returns:

Double.NaN if not valid

getLowerBound

default double getLowerBound()

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.

Returns:

Double.NaN if not valid

getUpperBound

default double getUpperBound()

Get the upper bound (if available).

Returns:

Double.NaN if not valid

allLowerBound

double allLowerBound()

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.

Returns:

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

advance

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

Returns:

The iterator itself.