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.

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).

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
void	add(double distance, DBIDRef id) Add a distance-id pair to the heap unless the distance is too large.
void	add(Double distance, DBIDRef id) Deprecated.
void	add(DoubleDistanceDBIDPair e) Add a pair to the heap.
void	add(DoubleDistance dist, DBIDRef id) Deprecated. if you know your distances are double-valued, you should be using the primitive type.
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()
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.

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.

add

public final void add(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:

add in interface DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

add

@Deprecated
public final void add(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:

add in interface DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

heapModified

protected void heapModified()

add

public void add(DoubleDistanceDBIDPair e)

Description copied from class: AbstractKNNHeap

Add a pair to the heap.

Specified by:

add in interface DoubleDistanceKNNHeap

Specified by:

add in class AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>

Parameters:

e - Pair to add.

add

@Deprecated
public void add(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:

add in interface DoubleDistanceKNNHeap

Specified by:

add 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