Package elki.index.tree.metrical.vptree

Class GNAT<O>

java.lang.Object

elki.index.tree.metrical.vptree.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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	GNAT.Factory<O extends NumberVector>	Index Factory
class	GNAT.GNATKNNDBIDSearcher	kNN search for the VP-Tree.
class	GNAT.GNATKNNObjectSearcher	kNN search for the VP-Tree.
static class	GNAT.GNATKNNSearcher	kNN query for the mvp-tree.
class	GNAT.GNATPriorityDBIDSearcher	Range search for the VP-tree.
class	GNAT.GNATPriorityObjectSearcher	Range search for the VP-tree.
class	GNAT.GNATPrioritySearcher<T>	priority search query for mvp-tree
class	GNAT.GNATRangeDBIDSearcher	Range search for the VP-tree.
class	GNAT.GNATRangeObjectSearcher	Range search for the VP-tree.
static class	GNAT.GNATRangeSearcher	range query for the mvp-tree
(package private) static class	GNAT.Node	The Node class saves the important information for the each node
private static class	GNAT.PrioritySearchBranch	Search position for priority search.

Field Summary

Fields

Modifier and Type	Field	Description
protected long	distComputations	Counter for distance computations.
(package private) Distance<? super O>	distFunc	Distance Function to use
(package private) DistanceQuery<O>	distQuery	Actual distance query on the Data
private static Logging	LOG	Class logger.
(package private) int	numberVPs	Sample size for selecting vantage points
(package private) RandomFactory	random	Random factory for selecting vantage points
protected Relation<O>	relation	The representation we are bound to.
(package private) GNAT.Node	root	Root node from the tree
(package private) ModifiableDoubleDBIDList	sorted	Distance storage for building

Constructor Summary

Constructors

Constructor	Description
GNAT(Relation<O> relation, Distance<? super O> distance, RandomFactory random, int numberVPs)	Constructor.

Method Summary

Modifier and Type	Method	Description
private void	buildTree(GNAT.Node current, DBIDs content, int vps)	builds the tree recursively
private double	distance(DBIDRef a, DBIDRef b)	Compute a distance, and count.
private double	distance(O a, DBIDRef b)	Compute a distance, and count.
private ArrayDBIDs	findVantagePoints(DBIDs content, int vps)	Finds a vantage points in the DBIDs between left and right
void	initialize()	Initialize the index.
private static boolean	intersect(double l1, double u1, double l2, double u2)	check intersection of 2 intervals
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.

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.

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

sorted

ModifiableDoubleDBIDList sorted

Distance storage for building

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

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 interface DistancePriorityIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum search range (may be Double.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 interface DistancePriorityIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum search range (may be Double.POSITIVE_INFINITY

flags - Optimizer hints

Returns:

Priority searcher

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