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 Factoryclass
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-treeclass
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 nodeprivate 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 Dataprivate static Logging
LOG
Class logger.(package private) int
numberVPs
Sample size for selecting vantage points(package private) RandomFactory
random
Random factory for selecting vantage pointsprotected 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
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
buildTree(GNAT.Node current, DBIDs content, int vps)
builds the tree recursivelyprivate 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 rightvoid
initialize()
Initialize the index.private static boolean
intersect(double l1, double u1, double l2, double u2)
check intersection of 2 intervalsKNNSearcher<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.
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger.
-
distComputations
protected long distComputations
Counter for distance computations.
-
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 constructiondistance
- 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 interfaceIndex
-
distance
private double distance(DBIDRef a, DBIDRef b)
Compute a distance, and count.- Parameters:
a
- First objectb
- Second object- Returns:
- Distance
-
distance
private double distance(O a, DBIDRef b)
Compute a distance, and count.- Parameters:
a
- First objectb
- Second object- Returns:
- Distance
-
buildTree
private void buildTree(GNAT.Node current, DBIDs content, int vps)
builds the tree recursively- Parameters:
current
- current node to buildcontent
- data to indexvps
- 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 processvps
- 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 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
-
intersect
private static boolean intersect(double l1, double u1, double l2, double u2)
check intersection of 2 intervals- Parameters:
l1
- first lower boundu1
- first upper boundl2
- second lower boundu2
- 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 interfaceIndex
-
-