Package elki.index.idistance

Class InMemoryIDistanceIndex<O>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:
    Index, KNNIndex<O>, RangeIndex<O>
    @Reference(authors="C. Yu, B. C. Ooi, K. L. Tan, H. V. Jagadish",title="Indexing the distance: An efficient method to knn processing",booktitle="Proc. 27th Int. Conf. on Very Large Data Bases",url="http://www.vldb.org/conf/2001/P421.pdf",bibkey="DBLP:conf/vldb/OoiYTJ01") @Reference(authors="H. V. Jagadish, B. C. Ooi, K. L. Tan, C. Yu, R. Zhang",title="iDistance: An adaptive B+-tree based indexing method for nearest neighbor search",booktitle="ACM Transactions on Database Systems (TODS), 30(2)",url="https://doi.org/10.1145/1071610.1071612",bibkey="DBLP:journals/tods/JagadishOTYZ05")
public class InMemoryIDistanceIndex<O>
extends AbstractRefiningIndex<O>
implements RangeIndex<O>, KNNIndex<O>
    In-memory iDistance index, a metric indexing method using a reference point embedding.

    Important note: we are currently using a different query strategy. The original publication discusses queries based on repeated radius queries. We use a strategy based on shrinking spheres, iteratively refined starting with the closes reference point. We also do not use a B+-tree as data structure, but simple in-memory lists. Therefore, we cannot report page accesses needed.

    Feel free to contribute improved query strategies. All the code is essentially here, you only need to query every reference point list, not just the best.

    Reference:

    C. Yu, B. C. Ooi, K. L. Tan, H. V. Jagadish
    Indexing the Distance: An Efficient Method to KNN Processing.
    In Proceedings of the 27th International Conference on Very Large Data Bases

    H. V. Jagadish, B. C. Ooi, K. L. Tan, C. Yu, R. Zhang
    iDistance: An adaptive B+-tree based indexing method for nearest neighbor search.
    ACM Transactions on Database Systems (TODS), 30(2).

    Since:
    0.7.0
    Author:
    Erich Schubert

    • Constructor Detail

      • InMemoryIDistanceIndex

        public InMemoryIDistanceIndex​(Relation<O> relation,
                              DistanceQuery<O> distance,
                              KMedoidsInitialization<O> initialization,
                              int numref)
        Constructor.
        Parameters:
        relation - Data relation
        distance - Distance
        initialization - Initialization method
        numref - Number of reference points

    • 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

      • 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 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 maxradius,
                                      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 RangeIndex<O>
        Parameters:
        distanceQuery - Distance query
        maxradius - Maximum range
        flags - Hints for the optimizer
        Returns:
        KNN Query object or null

      • getDistance

        private Distance<? super O> getDistance()
        Distance function.
        Returns:
        Distance function

      • 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
        Overrides:
        logStatistics in class AbstractRefiningIndex<O>

      • rankReferencePoints

        protected static <O> DoubleIntPair[] rankReferencePoints​(DistanceQuery<O> distanceQuery,
                                                         O obj,
                                                         ArrayDBIDs referencepoints)
        Sort the reference points by distance to the query object
        Parameters:
        distanceQuery - Distance query
        obj - Query object
        referencepoints - Iterator for reference points
        Returns:
        Sorted array.

      • binarySearch

        protected static void binarySearch​(ModifiableDoubleDBIDList index,
                                   DoubleDBIDListIter iter,
                                   double val)
        Seek an iterator to the desired position, using binary search.
        Parameters:
        index - Index to search
        iter - Iterator
        val - Distance to search to