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