de.lmu.ifi.dbs.elki.index.distancematrix

Class PrecomputedDistanceMatrix<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.distancematrix.PrecomputedDistanceMatrix<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

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

public class PrecomputedDistanceMatrix<O>
extends java.lang.Object
implements DistanceIndex<O>, RangeIndex<O>, KNNIndex<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 and Description
static class	PrecomputedDistanceMatrix.Factory<O> Factory for the index.
private class	PrecomputedDistanceMatrix.PrecomputedDistanceQuery Distance query using the precomputed matrix.
private class	PrecomputedDistanceMatrix.PrecomputedKNNQuery kNN query using the distance matrix.
private class	PrecomputedDistanceMatrix.PrecomputedRangeQuery Range query using the distance matrix.

Field Summary

Fields

Modifier and Type	Field and Description
protected DistanceFunction<? super O>	distanceFunction Nested distance function.
protected DistanceQuery<O>	distanceQuery Nested distance query.
private DBIDRange	ids DBID range.
private static Logging	LOG Class logger.
private double[]	matrix Distance matrix.
protected Relation<O>	relation Data relation.
private int	size Size of DBID range.

Constructor Summary

Constructors

Constructor and Description
PrecomputedDistanceMatrix(Relation<O> relation, DBIDRange range, DistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Modifier and Type	Method and Description
DistanceQuery<O>	getDistanceQuery(DistanceFunction<? super O> distanceFunction, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
java.lang.String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
private int	getOffset(int x, int y) Array offset computation.
RangeQuery<O>	getRangeQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a range query object for the given distance query and k.
java.lang.String	getShortName() A short name for the result, useful for file names.
void	initialize() Initialize the index.
void	logStatistics() Send statistics to the logger, if enabled.
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.

relation

protected final Relation<O> relation

Data relation.

distanceFunction

protected final DistanceFunction<? super O> distanceFunction

Nested distance function.

distanceQuery

protected DistanceQuery<O> distanceQuery

Nested distance query.

matrix

private double[] matrix

Distance matrix.

ids

private DBIDRange ids

DBID range.

size

private int size

Size of DBID range.

Constructor Detail

PrecomputedDistanceMatrix

public PrecomputedDistanceMatrix(Relation<O> relation,
                                 DBIDRange range,
                                 DistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

relation - Data relation

range - DBID range

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

getLongName

public java.lang.String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Returns:

result name

getShortName

public java.lang.String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Returns:

result name

getDistanceQuery

public DistanceQuery<O> getDistanceQuery(DistanceFunction<? super O> distanceFunction,
                                         java.lang.Object... hints)

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.

hints - Hints for the optimizer

Returns:

KNN Query object or null

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                               java.lang.Object... hints)

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:

getKNNQuery in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRangeQuery

public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery,
                                   java.lang.Object... hints)

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:

getRangeQuery in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null