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.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods 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)
-
-
-
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 interfaceIndex
-
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 parametery
- 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 interfaceIndex
-
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 interfaceDistanceIndex<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 interfaceDistancePriorityIndex<O>
- Specified by:
kNNByObject
in interfaceKNNIndex<O>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum value of kflags
- 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!
-
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 interfaceDistancePriorityIndex<O>
- Specified by:
rangeByObject
in interfaceRangeIndex<O>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum rangeflags
- 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 interfaceRangeIndex<O>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum rangeflags
- 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 interfaceDistancePriorityIndex<O>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum search range (may beDouble.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 interfaceDistancePriorityIndex<O>
- Parameters:
distanceQuery
- Distance querymaxrange
- Maximum search range (may beDouble.POSITIVE_INFINITY
flags
- Optimizer hints- Returns:
- Priority searcher
-
-