de.lmu.ifi.dbs.elki.distance.distanceresultlist

Class DoubleDistanceKNNHeap

java.lang.Object

de.lmu.ifi.dbs.elki.distance.distanceresultlist.AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>

de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap

All Implemented Interfaces:

KNNHeap<DoubleDistance>

public class DoubleDistanceKNNHeap
extends AbstractKNNHeap<DoubleDistanceDBIDPair,DoubleDistance>

Heap for collecting double-valued KNN instances. See also: KNNUtil.newHeap(de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction<?, 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;
 DoubleDistanceKNNHeap heap = new DoubleDistanceKNNHeap(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	DoubleDistanceKNNHeap.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.distance.distanceresultlist.AbstractKNNHeap

heap

Constructor Summary

Constructors

Constructor and Description
DoubleDistanceKNNHeap(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) Add a distance-id pair to the heap unless the distance is too large.
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()
DoubleDistanceKNNList	toKNNList() Serialize to a DoubleDistanceKNNList.

Methods inherited from class de.lmu.ifi.dbs.elki.distance.distanceresultlist.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

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

DoubleDistanceKNNHeap

public DoubleDistanceKNNHeap(int k)

Constructor. See also: KNNUtil.newHeap(de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction<?, D>, int)!

Parameters:

k - Heap size

Method Detail

toKNNList

public DoubleDistanceKNNList toKNNList()

Serialize to a DoubleDistanceKNNList. This empties the heap!

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.

Parameters:

distance - Distance value

id - ID number

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.

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

Parameters:

dist - Distance value

id - ID number

doubleKNNDistance

public double doubleKNNDistance()

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

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.

Returns:

Maximum distance