vptree

package module

v0.0.0-...-6b5b63c Latest Latest Go to latest Published: Feb 21, 2017 License: Unlicense Imports: 3 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/dahernan/vptree

Links

Open Source Insights

README ¶

vptree

vptree is a port of Steve Hanov's C++ implementation of Vantage-point trees to the Go programming language. Vantage-point trees are useful for nearest-neighbour searches in high-dimensional metric spaces.

This is a modified version https://github.com/dgryski/go-simstore/vptree

It has been customized to search specifically for Items consisting of a 64-bit signature and an string ID using Hamming distance as the distance measure.

Also it has no external dependencies.

Documentation ¶

Index ¶

func HammingDistance(v1 uint64, v2 uint64) int
func L2(p, q []float64) float64
type Item
type Point
type VPTree
- func New(items []Item) (t *VPTree)
- func (vp *VPTree) Search(target []float64, k int) (results []Item, distances []float64)

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

func HammingDistance ¶

func HammingDistance(v1 uint64, v2 uint64) int

func L2 ¶

func L2(p, q []float64) float64

L2 returns the L2 distance of two points.

Types ¶

type Item ¶

type Item struct {
	Sig  []float64
	ID   string
	Name string
}

type Point ¶

type Point []float64

type VPTree ¶

type VPTree struct {
	// contains filtered or unexported fields
}

A VPTree struct represents a Vantage-point tree. Vantage-point trees are useful for nearest-neighbour searches in high-dimensional metric spaces.

func New ¶

func New(items []Item) (t *VPTree)

New creates a new VP-tree using the metric and items provided. The metric measures the distance between two items, so that the VP-tree can find the nearest neighbour(s) of a target item.

func (*VPTree) Search ¶

func (vp *VPTree) Search(target []float64, k int) (results []Item, distances []float64)

Search searches the VP-tree for the k nearest neighbours of target. It returns the up to k narest neighbours and the corresponding distances in order of least distance to largest distance.

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL