Package elki.index.distancematrix
Class PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher
- java.lang.Object
-
- elki.index.distancematrix.PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher
-
- All Implemented Interfaces:
DBIDIter
,DBIDRef
,KNNSearcher<DBIDRef>
,PrioritySearcher<DBIDRef>
,RangeSearcher<DBIDRef>
,Iter
,QuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>
- Enclosing class:
- PrecomputedDistanceMatrix<O>
public class PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher extends java.lang.Object implements PrioritySearcher<DBIDRef>, QuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>
Range query using the distance matrix.- Author:
- Erich Schubert
-
-
Field Summary
Fields Modifier and Type Field Description (package private) double[]
dists
Sorted distances(package private) int[]
idx
Object indexes(package private) DBIDArrayIter
it
Iterator for mapping.(package private) int
lbsorted
"side effect" sorting positions(package private) int
off
Current position(package private) int
sorted
Sorting position(package private) double
threshold
Query threshold(package private) int
upsorted
"side effect" sorting positions
-
Constructor Summary
Constructors Constructor Description PrecomputedDistancePrioritySearcher()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description PrioritySearcher<DBIDRef>
advance()
Moves the iterator forward to the next entry.double
allLowerBound()
Lower bound for all subsequent instances (that have been completely explored).int
compare(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int i, int j)
Compare two elements.double
computeExactDistance()
Compute the exact distance to the current candidate.PrioritySearcher<DBIDRef>
decreaseCutoff(double threshold)
Decrease the cutoff threshold.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.void
isSorted(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int begin, int end)
Notification callback that an array is completely sorted.private void
partialSort(int target)
Partially sort the data.PrioritySearcher<DBIDRef>
search(DBIDRef query)
Start search with a new object.void
swap(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int i, int j)
Swap the two elements at positions i and j.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
-
Methods inherited from interface elki.database.query.range.RangeSearcher
getRange
-
-
-
-
Field Detail
-
it
DBIDArrayIter it
Iterator for mapping.
-
off
int off
Current position
-
sorted
int sorted
Sorting position
-
lbsorted
int lbsorted
"side effect" sorting positions
-
upsorted
int upsorted
"side effect" sorting positions
-
threshold
double threshold
Query threshold
-
idx
int[] idx
Object indexes
-
dists
double[] dists
Sorted distances
-
-
Method Detail
-
search
public PrioritySearcher<DBIDRef> search(DBIDRef query)
Description copied from interface:PrioritySearcher
Start search with a new object.- Specified by:
search
in interfacePrioritySearcher<DBIDRef>
- Parameters:
query
- Query object- Returns:
this
, for chaining
-
partialSort
private void partialSort(int target)
Partially sort the data.- Parameters:
target
- Target
-
advance
public PrioritySearcher<DBIDRef> advance()
Description copied from interface:Iter
Moves the iterator forward to the next entry.
-
valid
public boolean valid()
Description copied from interface:Iter
Returns true if the iterator currently points to a valid object.
-
decreaseCutoff
public PrioritySearcher<DBIDRef> 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<DBIDRef>
- Parameters:
threshold
- Threshold parameter- Returns:
- this, for chaining
-
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
-
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<DBIDRef>
- Returns:
- Distance
-
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<DBIDRef>
- 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<DBIDRef>
- 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<DBIDRef>
- 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<DBIDRef>
- 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<DBIDRef>
- Returns:
- lower bound;
0
if no guarantees (e.g., linear scan)
-
compare
public int compare(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int i, int j)
Description copied from interface:QuickSelect.Adapter
Compare two elements.- Specified by:
compare
in interfaceQuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>
- Parameters:
data
- Data structurei
- Position ij
- Position j- Returns:
-1,0,+1
when the element at position i is smaller, equal, or greater than that at position j.
-
swap
public void swap(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int i, int j)
Description copied from interface:QuickSelect.Adapter
Swap the two elements at positions i and j.- Specified by:
swap
in interfaceQuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>
- Parameters:
data
- Data structurei
- Position ij
- Position j
-
isSorted
public void isSorted(PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher data, int begin, int end)
Description copied from interface:QuickSelect.Adapter
Notification callback that an array is completely sorted.- Specified by:
isSorted
in interfaceQuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>
- Parameters:
data
- Data structurebegin
- Begin of sorted intervalend
- End of sorted interval
-
-