Package elki.index.distancematrix

Class PrecomputedDistanceMatrix<O>

java.lang.Object

elki.index.distancematrix.PrecomputedDistanceMatrix<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

DistanceIndex<O>, DistancePriorityIndex<O>, Index, KNNIndex<O>, RangeIndex<O>

public class PrecomputedDistanceMatrix<O>
extends java.lang.Object
implements DistanceIndex<O>, RangeIndex<O>, KNNIndex<O>, DistancePriorityIndex<O>

Distance matrix, for precomputing similarity for a small data set.

This class uses a linear memory layout (not a ragged array), and assumes symmetry as well as strictness. This way, it only stores the upper triangle matrix with double precision. It has to store (n-1) * (n-2) distance values in memory, requiring 8 * (n-1) * (n-2) bytes. Since Java has a size limit of arrays of 31 bits (signed integer), we can store at most \(2^{16}\) objects (precisely, 65536 objects) in a single array, which needs about 16 GB of RAM.

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	PrecomputedDistanceMatrix.Factory<O>	Factory for the index.
class	PrecomputedDistanceMatrix.PrecomputedDistancePrioritySearcher	Range query using the distance matrix.
class	PrecomputedDistanceMatrix.PrecomputedDistanceQuery	Distance query using the precomputed matrix.
class	PrecomputedDistanceMatrix.PrecomputedKNNQuery	kNN query using the distance matrix.
class	PrecomputedDistanceMatrix.PrecomputedRangeQuery	Range query using the distance matrix.

Field Summary

Fields

Modifier and Type	Field	Description
protected Distance<? super O>	distance	Nested distance function.
private DBIDRange	ids	DBID range.
private static Logging	LOG	Class logger.
private double[]	matrix	Distance matrix.
protected java.lang.ref.WeakReference<Relation<O>>	refrelation	Data relation.

Constructor Summary

Constructors

Constructor	Description
PrecomputedDistanceMatrix(Relation<O> relation, DBIDRange range, Distance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
DistanceQuery<O>	getDistanceQuery(Distance<? super O> distanceFunction)	Get a KNN query object for the given distance query and k.
private int	getOffset(int x, int y)	Array offset computation.
void	initialize()	Initialize the index.
KNNSearcher<DBIDRef>	kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
KNNSearcher<O>	kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
void	logStatistics()	Send statistics to the logger, if enabled.
PrioritySearcher<DBIDRef>	priorityByDBID(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a priority search object.
PrioritySearcher<O>	priorityByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a priority search object.
RangeSearcher<DBIDRef>	rangeByDBID(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a range query object for the given distance query and k.
RangeSearcher<O>	rangeByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a range query object for the given distance query and k.
protected static int	triangleSize(int x)	Compute the size of a complete x by x triangle (minus diagonal)

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final Logging LOG

Class logger.

refrelation

protected final java.lang.ref.WeakReference<Relation<O>> refrelation

Data relation.

distance

protected final Distance<? super O> distance

Nested distance function.

matrix

private double[] matrix

Distance matrix.

ids

private DBIDRange ids

DBID range.

Constructor Detail

PrecomputedDistanceMatrix

public PrecomputedDistanceMatrix(Relation<O> relation,
                                 DBIDRange range,
                                 Distance<? super O> distance)

Constructor.

Parameters:

relation - Data relation

range - DBID range

distance - Distance function

Method Detail

initialize

public void initialize()

Description copied from interface: Index

Initialize the index. For static indexes, this is the moment the index is bulk loaded.

Specified by:

initialize in interface Index

triangleSize

protected static int triangleSize(int x)

Compute the size of a complete x by x triangle (minus diagonal)

Parameters:

x - Offset

Returns:

Size of complete triangle

getOffset

private int getOffset(int x,
                      int y)

Array offset computation.

Parameters:

x - X parameter

y - Y parameter

Returns:

Array offset

logStatistics

public void logStatistics()

Description copied from interface: Index

Send statistics to the logger, if enabled.

Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.

Specified by:

logStatistics in interface Index

getDistanceQuery

public DistanceQuery<O> getDistanceQuery(Distance<? super O> distanceFunction)

Description copied from interface: DistanceIndex

Get a KNN query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

getDistanceQuery in interface DistanceIndex<O>

Parameters:

distanceFunction - Distance function to use.

Returns:

KNN Query object or null

kNNByObject

public KNNSearcher<O> kNNByObject(DistanceQuery<O> distanceQuery,
                                  int maxk,
                                  int flags)

Description copied from interface: KNNIndex

Get a KNN query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

kNNByObject in interface DistancePriorityIndex<O>

Specified by:

kNNByObject in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

kNNByDBID

public KNNSearcher<DBIDRef> kNNByDBID(DistanceQuery<O> distanceQuery,
                                      int maxk,
                                      int flags)

Description copied from interface: KNNIndex

Get a KNN query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

kNNByDBID in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByObject

public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery,
                                      double maxrange,
                                      int flags)

Description copied from interface: RangeIndex

Get a range query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

rangeByObject in interface DistancePriorityIndex<O>

Specified by:

rangeByObject in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByDBID

public RangeSearcher<DBIDRef> rangeByDBID(DistanceQuery<O> distanceQuery,
                                          double maxrange,
                                          int flags)

Description copied from interface: RangeIndex

Get a range query object for the given distance query and k.

This function MAY return null, when the given distance is not supported!

Specified by:

rangeByDBID in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null

priorityByObject

public PrioritySearcher<O> priorityByObject(DistanceQuery<O> distanceQuery,
                                            double maxrange,
                                            int flags)

Description copied from interface: DistancePriorityIndex

Get a priority search object.

Specified by:

priorityByObject in interface DistancePriorityIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum search range (may be Double.POSITIVE_INFINITY

flags - Optimizer hints

Returns:

Priority searcher

priorityByDBID

public PrioritySearcher<DBIDRef> priorityByDBID(DistanceQuery<O> distanceQuery,
                                                double maxrange,
                                                int flags)

Description copied from interface: DistancePriorityIndex

Get a priority search object.

Specified by:

priorityByDBID in interface DistancePriorityIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum search range (may be Double.POSITIVE_INFINITY

flags - Optimizer hints

Returns:

Priority searcher