README
¶
Go package
- vptree : Vantage point tree for efficient exact or approximate k-nearest neighbor and range searches.
Implements the algorithm from: "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces" by Peter N. Yianilos
Documentation
¶
Overview ¶
Package vptree implements a 'vantage point tree' for exact or approximate nearest neighbor and range searches. The dataset consists of n d-dimensional points in a metric space. Points with identical positions are treated as unique entities. Any datatype that implements the Point interface can be handled.
See http://web.cs.iastate.edu/~honavar/nndatastructures.pdf : "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces" by Peter N. Yianilos
TODO: serialize/deserialize TODO: updates (insert/delete element)
Index ¶
- type Info
- type Point
- type VPTree
- func (t *VPTree) ApproximateKNN(query Point, k, nn int) ([]Point, []float32)
- func (t *VPTree) Info() Info
- func (t *VPTree) KNN(query Point, k int) ([]Point, []float32)
- func (t *VPTree) NN(query Point) (Point, float32)
- func (t *VPTree) RangeNN(query Point, r float32) ([]Point, []float32)
- func (t *VPTree) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Point ¶
type Point interface {
// Distance returns the distance between the receiver and p.
Distance(p Point) float32
}
Point in a metric space of arbitrary dimensions. The distance metric must fulfil the following requirements:
d(x, y) >= 0 d(x, y) = 0 if and only if x == y d(x, y) = d(y, x) d(x, z) <= d(x, y) + d(y, z) (triangle inequality)
Manhattan (Lⁱ norm) or Euclidian (L² norm) metrics are suitable. Using squared distances won't work as this violates the triangle equality.
type VPTree ¶
type VPTree struct {
// contains filtered or unexported fields
}
VPTree represents a vantage point tree.
func NewVPTree ¶
NewVPTree returns an initialized tree holding the given points. If desired the tree is optimized by trial and error for efficient search by finding the best vantage point layout. The higher nTrials is, the faster the search performance, but the slower the tree initialization.
func (*VPTree) ApproximateKNN ¶
ApproximateKNN returns the approximate k nearest neighbors to the query point, together with their respective distances. The nn parameter specifies the maximal number of nodes that are visited during the search, and can thus be used to limit the time spent searching. The results are sorted from nearest to farthest. If k > total number of samples in the tree, k is limited to the total number of samples.
func (*VPTree) KNN ¶
KNN returns the exact k nearest neighbors to the query point, together with their respective distances. The results are sorted from nearest to farthest. If k > total number of samples in the tree, k is limited to the total number of samples. When there is a tie for the farthest of the nearest neighbors, k won't increase to always return all of them.
func (*VPTree) NN ¶
NN returns the exact nearest neighbor to the query point, together with its distance.
Source Files