edu.stanford.math.plex4.metric.impl

Class ExplicitMetricSpace

java.lang.Object

edu.stanford.math.plex4.metric.impl.ExplicitMetricSpace

All Implemented Interfaces:

AbstractIntMetricSpace, AbstractObjectMetric<java.lang.Integer>, AbstractObjectMetricSpace<java.lang.Integer>, AbstractSearchableMetricSpace<java.lang.Integer>

public class ExplicitMetricSpace
extends java.lang.Object
implements AbstractSearchableMetricSpace<java.lang.Integer>

This class implements the AbstractIntMetricSpace interface. The distances between points is given by a distance matrix.

Author:

Andrew Tausz

Constructor Summary

Constructors

Constructor and Description
ExplicitMetricSpace(double[][] distanceMatrix) This constructor initializes the class with the given distance matrix.

Method Summary

Methods

Modifier and Type	Method and Description
double	distance(java.lang.Integer a, java.lang.Integer b) This function returns the distance between two points.
double	distance(int i, int j) This function returns the distance between the object at index i and the object at index j.
gnu.trove.TIntHashSet	getClosedNeighborhood(java.lang.Integer 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(java.lang.Integer queryPoint, int k) This function returns the indices of the k points that are closest to the given query point.
int	getNearestPointIndex(java.lang.Integer queryPoint) This function returns the index of the point within the metric space nearest to the given query point.
gnu.trove.TIntHashSet	getOpenNeighborhood(java.lang.Integer 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.
java.lang.Integer	getPoint(int index) This function returns the point at the specified index.
java.lang.Integer[]	getPoints() This function returns the set of points in the metric space as an array.
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

Constructor Detail

ExplicitMetricSpace

public ExplicitMetricSpace(double[][] distanceMatrix)

This constructor initializes the class with the given distance matrix. The supplied distance matrix must be square, and must define a valid metric. Ie. it must be symmetric, have zeros exactly on the diagonal, and satisfy the triangle inequality. Due to reasons of efficiency, these properties are not checked, and the user is required make sure that they hold. If the properties do not hold, no guarantees can be made about the behaviour of the algorithms.

Parameters:

distanceMatrix - the distance matrix to initialize with

See Also:

AbstractSearchableMetricSpace

Method Detail

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

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.

getClosedNeighborhood

public gnu.trove.TIntHashSet getClosedNeighborhood(java.lang.Integer 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<java.lang.Integer>

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

getKNearestNeighbors

public gnu.trove.TIntHashSet getKNearestNeighbors(java.lang.Integer 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<java.lang.Integer>

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(java.lang.Integer 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<java.lang.Integer>

Parameters:

queryPoint - the query point

Returns:

the index of the nearest point in the metric space

getOpenNeighborhood

public gnu.trove.TIntHashSet getOpenNeighborhood(java.lang.Integer 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<java.lang.Integer>

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

getPoint

public java.lang.Integer getPoint(int index)

Description copied from interface: AbstractObjectMetricSpace

This function returns the point at the specified index.

Specified by:

getPoint in interface AbstractObjectMetricSpace<java.lang.Integer>

Parameters:

index - the index of the point to retrieve

Returns:

the point at the given index

getPoints

public java.lang.Integer[] 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<java.lang.Integer>

Returns:

an array containing the points of the metric space

distance

public double distance(java.lang.Integer a,
              java.lang.Integer b)

Description copied from interface: AbstractObjectMetric

This function returns the distance between two points.

Specified by:

distance in interface AbstractObjectMetric<java.lang.Integer>

Parameters:

a - the first point

b - the second point

Returns:

the distance between the two points