LandmarkSelector

java.lang.Object
- edu.stanford.math.plex4.metric.landmark.LandmarkSelector<T>

Type Parameters:
T - the underlying type of the metric space

All Implemented Interfaces:

AbstractIntMetricSpace, AbstractObjectMetric<T>, AbstractObjectMetricSpace<T>, AbstractSearchableMetricSpace<T>

Direct Known Subclasses:

ExplicitLandmarkSelector, MaxMinLandmarkSelector, RandomLandmarkSelector
```
public abstract class LandmarkSelector<T>
extends java.lang.Object
implements AbstractSearchableMetricSpace<T>
```
This abstract class defines the functionality of a landmark set within an arbitrary finite metric space. A landmark set is used as an approximation to the whole metric space for efficiency purposes. It also tends to denoise the dataset under investigation. For further information about landmark sets, please consult the paper "Topological estimation using witness complexes", by Vin de Silva and Gunnar Carlsson.

A class that derives from LandmarkSelector must implement the computeLandmarkSet function which implements the computation of the landmark set.

Author:

Andrew Tausz

Field Summary

Fields
Modifier and Type	Field and Description
`protected int[]`	`indexMapping` This array holds the mapping between the indices of the landmark points, and the indices within the metric space.
`protected int`	`landmarkSetSize` This is the size of the landmark set
`protected AbstractSearchableMetricSpace<T>`	`metricSpace` This is the underlying metric space upon which the landmark set is build.

Constructor Summary

Constructors
Constructor and Description
`LandmarkSelector(AbstractSearchableMetricSpace<T> metricSpace, int landmarkSetSize)` This constructor initializes the landmark selector with a finite metric space, and a size parameter.
`LandmarkSelector(AbstractSearchableMetricSpace<T> metricSpace, int[] indices)`

Method Summary

Methods
Modifier and Type	Method and Description
`protected abstract int[]`	`computeLandmarkSet()` This function constructs the set of landmark points.
`double`	`distance(int i, int j)` This function returns the distance between the object at index i and the object at index j.
`double`	`distance(T a, T b)` This function returns the distance between two points.
`gnu.trove.TIntHashSet`	`getClosedNeighborhood(T queryPoint, double epsilon)` This function returns the set of indices of points that are contained in the closed ball of radius epsilon, centered at the specified query point.
`gnu.trove.TIntHashSet`	`getKNearestNeighbors(T queryPoint, int k)` This function returns the indices of the k points that are closest to the given query point.
`int`	`getLandmarkIndex(int i)` This function returns the index of the i-th landmark point.
`int[]`	`getLandmarkPoints()`
`double`	`getMaxDistanceFromPointsToLandmarks()` This function returns the maximum distance between points in the landmark selection and points not in the selection.
`int`	`getNearestPointIndex(T queryPoint)` This function returns the index of the point within the metric space nearest to the given query point.
`gnu.trove.TIntHashSet`	`getOpenNeighborhood(T queryPoint, double epsilon)` This function returns the set of indices of points that are contained in the open ball of radius epsilon, centered at the specified query point.
`T`	`getPoint(int index)` This function returns the point at the specified index.
`T[]`	`getPoints()` This function returns the set of points in the metric space as an array.
`AbstractSearchableMetricSpace<T>`	`getUnderlyingMetricSpace()`
`int`	`size()` This function returns the number of points in the metric space.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - metricSpace
```
protected final AbstractSearchableMetricSpace<T> metricSpace
```
    This is the underlying metric space upon which the landmark set is build.
  - landmarkSetSize
```
protected final int landmarkSetSize
```
    This is the size of the landmark set
  - indexMapping
```
protected final int[] indexMapping
```
    This array holds the mapping between the indices of the landmark points, and the indices within the metric space.
- Constructor Detail
  - LandmarkSelector
```
public LandmarkSelector(AbstractSearchableMetricSpace<T> metricSpace,
                int landmarkSetSize)
```
    This constructor initializes the landmark selector with a finite metric space, and a size parameter.
    
    Parameters:
    metricSpace - the metric space to build the landmarks set in
    landmarkSetSize - the size of the landmark set
  - LandmarkSelector
```
public LandmarkSelector(AbstractSearchableMetricSpace<T> metricSpace,
                int[] indices)
```
- Method Detail
  - getLandmarkIndex
```
public int getLandmarkIndex(int i)
```
    This function returns the index of the i-th landmark point.
    
    Parameters:
    i - the index within the set of landmark points
    
    Returns:
    the index of the i-th landmark point
  - getLandmarkPoints
```
public int[] getLandmarkPoints()
```
  - size
```
public int size()
```
    Description copied from interface: AbstractIntMetricSpace
    
    This function returns the number of points in the metric space.
    
    Specified by:
    
    size in interface AbstractIntMetricSpace
    
    Returns:
    the number of points in the metric space.
  - distance
```
public double distance(int i,
              int j)
```
    Description copied from interface: AbstractIntMetricSpace
    
    This function returns the distance between the object at index i and the object at index j.
    
    Specified by:
    
    distance in interface AbstractIntMetricSpace
    
    Parameters:
    i - the index of the first object
    j - the index of the second object
    
    Returns:
    the distance between the objects at the two given indices
  - distance
```
public double distance(T a,
              T b)
```
    Description copied from interface: AbstractObjectMetric
    
    This function returns the distance between two points.
    
    Specified by:
    
    distance in interface AbstractObjectMetric<T>
    
    Parameters:
    a - the first point
    b - the second point
    
    Returns:
    the distance between the two points
  - getPoint
```
public T getPoint(int index)
```
    Description copied from interface: AbstractObjectMetricSpace
    
    This function returns the point at the specified index.
    
    Specified by:
    
    getPoint in interface AbstractObjectMetricSpace<T>
    
    Parameters:
    index - the index of the point to retrieve
    
    Returns:
    the point at the given index
  - getUnderlyingMetricSpace
```
public AbstractSearchableMetricSpace<T> getUnderlyingMetricSpace()
```
  - getPoints
```
public T[] getPoints()
```
    Description copied from interface: AbstractObjectMetricSpace
    
    This function returns the set of points in the metric space as an array. The returned array satisfies the requirement that the indices of the points in the array are equal to the indices of the points within the metric space.
    
    Specified by:
    
    getPoints in interface AbstractObjectMetricSpace<T>
    
    Returns:
    an array containing the points of the metric space
  - computeLandmarkSet
```
protected abstract int[] computeLandmarkSet()
```
    This function constructs the set of landmark points. It must return an array of size landmarkSetSize, which contains the indices of the landmark points within the metric space.
    
    Returns:
    an array of indices corresponding to the landmark points in the metric space
  - getMaxDistanceFromPointsToLandmarks
```
public double getMaxDistanceFromPointsToLandmarks()
```
    This function returns the maximum distance between points in the landmark selection and points not in the selection. In other words, it returns R = max_{x in X} d(x, L), where d(x, L) = min_{l in L} d(x, l).
    
    Returns:
    the maximum distance between points in the landmark selection and points not in it
  - getClosedNeighborhood
```
public gnu.trove.TIntHashSet getClosedNeighborhood(T queryPoint,
                                          double epsilon)
```
    Description copied from interface: AbstractSearchableMetricSpace
    
    This function returns the set of indices of points that are contained in the closed ball of radius epsilon, centered at the specified query point. That is it returns all points satisfying d(p_i, q) <= epsilon, where q is the query point.
    
    Specified by:
    
    getClosedNeighborhood in interface AbstractSearchableMetricSpace<T>
    
    Parameters:
    queryPoint - the center of the closed ball
    epsilon - the radius of the closed ball
    
    Returns:
    the set of indices of points contained in the closed ball
  - getOpenNeighborhood
```
public gnu.trove.TIntHashSet getOpenNeighborhood(T queryPoint,
                                        double epsilon)
```
    Description copied from interface: AbstractSearchableMetricSpace
    
    This function returns the set of indices of points that are contained in the open ball of radius epsilon, centered at the specified query point. That is it returns all points satisfying d(p_i, q) < epsilon, where q is the query point.
    
    Specified by:
    
    getOpenNeighborhood in interface AbstractSearchableMetricSpace<T>
    
    Parameters:
    queryPoint - the center of the open ball
    epsilon - the radius of the open ball
    
    Returns:
    the set of indices of points contained in the open ball
  - getKNearestNeighbors
```
public gnu.trove.TIntHashSet getKNearestNeighbors(T queryPoint,
                                         int k)
```
    Description copied from interface: AbstractSearchableMetricSpace
    
    This function returns the indices of the k points that are closest to the given query point.
    
    Specified by:
    
    getKNearestNeighbors in interface AbstractSearchableMetricSpace<T>
    
    Parameters:
    queryPoint - the reference point
    k - the number of nearest neighbors to get
    
    Returns:
    the k-nearest neighbors of the query point
  - getNearestPointIndex
```
public int getNearestPointIndex(T queryPoint)
```
    Description copied from interface: AbstractSearchableMetricSpace
    
    This function returns the index of the point within the metric space nearest to the given query point.
    
    Specified by:
    
    getNearestPointIndex in interface AbstractSearchableMetricSpace<T>
    
    Parameters:
    queryPoint - the query point
    
    Returns:
    the index of the nearest point in the metric space

Class LandmarkSelector<T>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

metricSpace

landmarkSetSize

indexMapping

Constructor Detail

LandmarkSelector

LandmarkSelector

Method Detail

getLandmarkIndex

getLandmarkPoints

size

distance

distance

getPoint

getUnderlyingMetricSpace

getPoints

computeLandmarkSet

getMaxDistanceFromPointsToLandmarks

getClosedNeighborhood

getOpenNeighborhood

getKNearestNeighbors

getNearestPointIndex