Class GNAT<O>

  • Type Parameters:
    O - Object type indexed
    All Implemented Interfaces:
    DistancePriorityIndex<O>, Index, KNNIndex<O>, RangeIndex<O>

    @Reference(authors="S. Brin",
               title="Near Neighbor Search in Large Metric Spaces",
               booktitle="Proc. 21th Int. Conf. on Very Large Data Bases (VLDB)",
               url="http://www.vldb.org/conf/1995/P574.PDF",
               bibkey="DBLP:conf/vldb/Brin95")
    public class GNAT<O>
    extends java.lang.Object
    implements DistancePriorityIndex<O>
    Geometric Near-neighbor Access Tree (GNAT), also known as Multi Vantage Point Tree or MVP-Tree.

    In a Multi Vantage Point Tree the data is split into Voronoi Cells (Dirichlet Domain) defined by the vantage Points

    Reference:

    S. Brin
    Near Neighbor Search in Large Metric Spaces
    Proc. 21th Int. Conf. on Very Large Data Bases (VLDB)

    Since:
    0.8.0
    Author:
    Robert Gehde
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger.
      • distComputations

        protected long distComputations
        Counter for distance computations.
      • relation

        protected final Relation<O> relation
        The representation we are bound to.
      • distFunc

        Distance<? super O> distFunc
        Distance Function to use
      • distQuery

        DistanceQuery<O> distQuery
        Actual distance query on the Data
      • random

        RandomFactory random
        Random factory for selecting vantage points
      • numberVPs

        int numberVPs
        Sample size for selecting vantage points
      • root

        GNAT.Node root
        Root node from the tree
    • Constructor Detail

      • GNAT

        public GNAT​(Relation<O> relation,
                    Distance<? super O> distance,
                    RandomFactory random,
                    int numberVPs)
        Constructor.
        Parameters:
        relation - data for tree construction
        distance - distance function for tree construction
    • 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
      • distance

        private double distance​(DBIDRef a,
                                DBIDRef b)
        Compute a distance, and count.
        Parameters:
        a - First object
        b - Second object
        Returns:
        Distance
      • distance

        private double distance​(O a,
                                DBIDRef b)
        Compute a distance, and count.
        Parameters:
        a - First object
        b - Second object
        Returns:
        Distance
      • buildTree

        private void buildTree​(GNAT.Node current,
                               DBIDs content,
                               int vps)
        builds the tree recursively
        Parameters:
        current - current node to build
        content - data to index
        vps - number of vantage points to use
      • findVantagePoints

        private ArrayDBIDs findVantagePoints​(DBIDs content,
                                             int vps)
        Finds a vantage points in the DBIDs between left and right
        Parameters:
        content - content to process
        vps - Number of vantage points to choose
        Returns:
        vantage point
      • 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
      • intersect

        private static boolean intersect​(double l1,
                                         double u1,
                                         double l2,
                                         double u2)
        check intersection of 2 intervals
        Parameters:
        l1 - first lower bound
        u1 - first upper bound
        l2 - second lower bound
        u2 - second upper bound
        Returns:
        if intervals intersect
      • 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