de.lmu.ifi.dbs.elki.database.ids.generic

Class DoubleDistanceDBIDPairKNNHeap

java.lang.Object

de.lmu.ifi.dbs.elki.database.ids.generic.AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>

de.lmu.ifi.dbs.elki.database.ids.generic.DoubleDistanceDBIDPairKNNHeap

All Implemented Interfaces:

DoubleDistanceKNNHeap, KNNHeap<DoubleDistance>

public class DoubleDistanceDBIDPairKNNHeap
extends AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>
implements DoubleDistanceKNNHeap

Heap for collecting double-valued KNN instances. See also: DBIDUtil.newHeap(D, int)! Experiments have shown that it can be much more performant to track the knndistance outside of the heap, and do comparisons on the stack:

 double knndist = Double.POSITIVE_INFINITY;
 DoubleDistanceDBIDPairKNNHeap heap = new DoubleDistanceDBIDPairKNNHeap(k);
 for (DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
   double dist = computeDistance(iditer, ...);
   if (dist < knndist) {
     heap.add(dist, iditer);
     if (heap.size() >= k) {
       max = heap.doubleKNNDistance();
     }
   }    
 }
 
 

The reason probably is that knndist resides on the stack and can be better optimized by the hotspot compiler.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	DoubleDistanceDBIDPairKNNHeap.Comp Comparator to use.
protected static class	DoubleDistanceDBIDPairKNNHeap.RComp Comparator to use.

Field Summary

Fields

Modifier and Type	Field and Description
static Comparator<DoubleDistanceDBIDPair>	COMPARATOR Comparator class.
protected double	knndistance Cached distance to k nearest neighbor (to avoid going through AbstractKNNHeap.peek() too often).
static Comparator<DoubleDistanceDBIDPair>	REVERSE_COMPARATOR Reverse comparator.

Fields inherited from class de.lmu.ifi.dbs.elki.database.ids.generic.AbstractKNNHeap

heap

Constructor Summary

Constructors

Constructor and Description
DoubleDistanceDBIDPairKNNHeap(int k) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
double	doubleKNNDistance() Get the distance to the k nearest neighbor, or maxdist otherwise.
DoubleDistance	getKNNDistance() Deprecated. if you know your distances are double-valued, you should be using the primitive type.
protected void	heapModified()
double	insert(double distance, DBIDRef id) Add a distance-id pair to the heap unless the distance is too large.
void	insert(Double distance, DBIDRef id) Deprecated.
void	insert(DoubleDistanceDBIDPair e) Add a pair to the heap.
void	insert(DoubleDistance dist, DBIDRef id) Deprecated. if you know your distances are double-valued, you should be using the primitive type.
DoubleDistanceDBIDPairKNNList	toKNNList() Serialize to a DoubleDistanceDBIDPairKNNList.

Methods inherited from class de.lmu.ifi.dbs.elki.database.ids.generic.AbstractKNNHeap

clear, getK, isEmpty, peek, poll, size

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap

peek, poll

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap

clear, getK, isEmpty, size

Field Detail

COMPARATOR

public static final Comparator<DoubleDistanceDBIDPair> COMPARATOR

Comparator class.

REVERSE_COMPARATOR

public static final Comparator<DoubleDistanceDBIDPair> REVERSE_COMPARATOR

Reverse comparator.

knndistance

protected double knndistance

Cached distance to k nearest neighbor (to avoid going through AbstractKNNHeap.peek() too often).

Constructor Detail

DoubleDistanceDBIDPairKNNHeap

public DoubleDistanceDBIDPairKNNHeap(int k)

Constructor. See also: DBIDUtil.newHeap(D, int)!

Parameters:

k - Heap size

Method Detail

toKNNList

public DoubleDistanceDBIDPairKNNList toKNNList()

Serialize to a DoubleDistanceDBIDPairKNNList. This empties the heap!

Specified by:

toKNNList in interface DoubleDistanceKNNHeap

Specified by:

toKNNList in interface KNNHeap<DoubleDistance>

Returns:

KNNList with the heaps contents.

insert

public final double insert(double distance,
            DBIDRef id)

Add a distance-id pair to the heap unless the distance is too large. Compared to the super.add() method, this often saves the pair construction.

Specified by:

insert in interface DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

Returns:

knn distance.

insert

@Deprecated
public final void insert(Double distance,
                     DBIDRef id)

Deprecated.

Add a distance-id pair to the heap unless the distance is too large. Compared to the super.add() method, this often saves the pair construction.

Specified by:

insert in interface DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

heapModified

protected void heapModified()

insert

public void insert(DoubleDistanceDBIDPair e)

Description copied from class: AbstractKNNHeap

Add a pair to the heap.

Specified by:

insert in interface DoubleDistanceKNNHeap

Specified by:

insert in class AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>

Parameters:

e - Pair to add.

insert

@Deprecated
public void insert(DoubleDistance dist,
                     DBIDRef id)

Deprecated. if you know your distances are double-valued, you should be using the primitive type.

Add a distance-id pair to the heap unless the distance is too large. Compared to the super.add() method, this often saves the pair construction.

Specified by:

insert in interface DoubleDistanceKNNHeap

Specified by:

insert in interface KNNHeap<DoubleDistance>

Parameters:

dist - Distance value

id - ID number

doubleKNNDistance

public double doubleKNNDistance()

Get the distance to the k nearest neighbor, or maxdist otherwise.

Specified by:

doubleKNNDistance in interface DoubleDistanceKNNHeap

Returns:

Maximum distance

getKNNDistance

@Deprecated
public DoubleDistance getKNNDistance()

Deprecated. if you know your distances are double-valued, you should be using the primitive type.

Get the distance to the k nearest neighbor, or maxdist otherwise.

Specified by:

getKNNDistance in interface DoubleDistanceKNNHeap

Specified by:

getKNNDistance in interface KNNHeap<DoubleDistance>

Returns:

Maximum distance