Package elki.index.tree.metrical.vptree

Class VPTree<O>

java.lang.Object

elki.index.tree.metrical.vptree.VPTree<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

DistancePriorityIndex<O>, Index, KNNIndex<O>, RangeIndex<O>

@Reference(authors="P. N. Yianilos",
           title="Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces",
           booktitle="Proc. ACM/SIGACT-SIAM Symposium on Discrete Algorithms",
           url="http://dl.acm.org/citation.cfm?id=313559.313789",
           bibkey="DBLP:conf/soda/Yianilos93")
public class VPTree<O>
extends java.lang.Object
implements DistancePriorityIndex<O>

Vantage Point Tree with no additional information

In a Vantage Point Tree the data is split at the median distance to a vantage point at every node.

The distance function in the original paper was bounded to have a limited tau size. In this class the function is not bounded, as we can just limit tau to Double.MAX_VALUE

Reference:

P. N. Yianilos
Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces
Proc. ACM/SIGACT-SIAM Symposium on Discrete Algorithms

Since:

0.8.0

Author:

Robert Gehde, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	VPTree.Builder	Build the VP-Tree
static class	VPTree.Factory<O extends NumberVector>	Index factory for the VP-Tree
protected static class	VPTree.Node	The Node Class saves the important information for the each Node
class	VPTree.VPTreeKNNDBIDSearcher	kNN search for the VP-Tree.
class	VPTree.VPTreeKNNObjectSearcher	kNN search for the VP-Tree.
static class	VPTree.VPTreeKNNSearcher	kNN search for the VP-Tree.
class	VPTree.VPTreePriorityDBIDSearcher	Range search for the VP-tree.
class	VPTree.VPTreePriorityObjectSearcher	Range search for the VP-tree.
class	VPTree.VPTreePrioritySearcher<Q>	Priority search for the VP-Tree.
class	VPTree.VPTreeRangeDBIDSearcher	Range search for the VP-tree.
class	VPTree.VPTreeRangeObjectSearcher	Range search for the VP-tree.
static class	VPTree.VPTreeRangeSearcher	Range search for the VP-tree.

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor	Description
VPTree(Relation<O> relation, Distance<? super O> distance, int leafsize)	Constructor with default values, used by EmpiricalQueryOptimizer
VPTree(Relation<O> relation, Distance<? super O> distance, RandomFactory random, int sampleSize, int truncate)	Constructor.

Method Summary

Modifier and Type	Method	Description
private double	distance(DBIDRef a, DBIDRef b)	Compute a distance, and count.
private double	distance(O a, DBIDRef b)	Compute a distance, and count.
void	initialize()	Initialize the index.
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.

relation

protected final Relation<O> relation

The representation we are bound to.

distFunc

Distance<? super O> distFunc

Distance Function to use

distQuery

private DistanceQuery<O> distQuery

Actual distance query on the Data

random

RandomFactory random

Random factory for selecting vantage points

sampleSize

int sampleSize

Sample size for selecting vantage points

truncate

int truncate

Truncation parameter

distComputations

long distComputations

Counter for distance computations.

root

VPTree.Node root

Root node from the tree

Constructor Detail

VPTree

public VPTree(Relation<O> relation,
              Distance<? super O> distance,
              int leafsize)

Constructor with default values, used by EmpiricalQueryOptimizer

Parameters:

relation - data for tree construction

distance - distance function for tree construction

leafsize - Leaf size and sample size (simpler parameterization)

VPTree

public VPTree(Relation<O> relation,
              Distance<? super O> distance,
              RandomFactory random,
              int sampleSize,
              int truncate)

Constructor.

Parameters:

relation - data for tree construction

distance - distance function for tree construction

random - Random generator for sampling

sampleSize - Sample size for finding the vantage point

truncate - Leaf size threshold

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

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

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