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

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.ids.DBIDIter

addTo

Methods inherited from interface elki.database.ids.DBIDRef

equals, hashCode

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

Constructor Detail

PrecomputedDistancePrioritySearcher

public PrecomputedDistancePrioritySearcher()

Method Detail

search

public PrioritySearcher<DBIDRef> search(DBIDRef query)

Description copied from interface: PrioritySearcher

Start search with a new object.

Specified by:

search in interface PrioritySearcher<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.

Specified by:

advance in interface DBIDIter

Specified by:

advance in interface Iter

Specified by:

advance in interface PrioritySearcher<DBIDRef>

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.

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 interface PrioritySearcher<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 interface DBIDRef

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 interface PrioritySearcher<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 interface PrioritySearcher<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 interface PrioritySearcher<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 interface PrioritySearcher<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 interface PrioritySearcher<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 interface PrioritySearcher<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 interface QuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>

Parameters:

data - Data structure

i - Position i

j - 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 interface QuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>

Parameters:

data - Data structure

i - Position i

j - 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 interface QuickSelect.Adapter<PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher>

Parameters:

data - Data structure

begin - Begin of sorted interval

end - End of sorted interval