kdtree

README

KDTree

Golang implementation of KD tree (https://en.wikipedia.org/wiki/K-d_tree) data structure

Getting started

Use go tool to install the package in your packages tree:

go get github.com/hongshibao/go-kdtree

Then you can use it in import section of your Go programs:

import "github.com/hongshibao/go-kdtree"

The package name is kdtree.

Basic example

First you need to implement the Point interface:

type Point interface {
	// Return the total number of dimensions
	Dim() int
	// Return the value X_{dim}, dim is started from 0
	GetValue(dim int) float64
	// Return the distance between two points
	Distance(p Point) float64
	// Return the distance between the point and the plane X_{dim}=val
	PlaneDistance(val float64, dim int) float64
}

Here is an example of implementing Point interface with square of Euclidean distance as the Distance definition:

type EuclideanPoint struct {
	Point
	Vec []float64
}

func (p *EuclideanPoint) Dim() int {
	return len(p.Vec)
}

func (p *EuclideanPoint) GetValue(dim int) float64 {
	return p.Vec[dim]
}

func (p *EuclideanPoint) Distance(other Point) float64 {
	var ret float64
	for i := 0; i < p.Dim(); i++ {
		tmp := p.GetValue(i) - other.GetValue(i)
		ret += tmp * tmp
	}
	return ret
}

func (p *EuclideanPoint) PlaneDistance(val float64, dim int) float64 {
	tmp := p.GetValue(dim) - val
	return tmp * tmp
}

Now you can create KD-tree from a list of points and get a list of k nearest neighbours for a target point:

func NewEuclideanPoint(vals ...float64) *EuclideanPoint {
	ret := &EuclideanPoint{}
	for _, val := range vals {
		ret.Vec = append(ret.Vec, val)
	}
	return ret
}

func main() {
	p1 := NewEuclideanPoint(0.0, 0.0, 0.0)
	p2 := NewEuclideanPoint(0.0, 0.0, 1.0)
	p3 := NewEuclideanPoint(0.0, 1.0, 0.0)
	p4 := NewEuclideanPoint(1.0, 0.0, 0.0)
	points := make([]Point, 0)
	points = append(points, p1)
	points = append(points, p2)
	points = append(points, p3)
	points = append(points, p4)
	tree := NewKDTree(points)
	targetPoint := NewEuclideanPoint(0.0, 0.0, 0.1)
	neighbours := tree.KNN(targetPoint, 2)
	for idx, p := range neighbours {
		fmt.Printf("Point %d: (%f", idx, p.GetValue(0))
		for i := 1; i < p.Dim(); i++ {
			fmt.Printf(", %f", p.GetValue(i))
		}
		fmt.Println(")")
	}
}

The returned k nearest neighbours are sorted by their distance with the target point.

Documentation

Index

• type KDTree
  • func NewKDTree(points []Point) *KDTree
  • func (t *KDTree) Dim() int
  • func (t *KDTree) KNN(target Point, k int) []Point
• type Point
• type PointBase
  • func NewPointBase(vals []float64) PointBase
  • func (b PointBase) Dim() int
  • func (b PointBase) GetGroupLabel() string
  • func (b PointBase) GetLabel() string
  • func (b PointBase) GetSequenceDimOne() int64
  • func (b PointBase) GetSequenceDimTwo() int64
  • func (b PointBase) GetSequenceLengthOne() int64
  • func (b PointBase) GetSequenceLengthTwo() int64
  • func (b PointBase) GetValue(dim int) float64
  • func (b PointBase) GetValues() []float64

Types

type KDTree

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

func NewKDTree

func NewKDTree(points []Point) *KDTree

func (*KDTree) Dim

func (t *KDTree) Dim() int

func (*KDTree) KNN

func (t *KDTree) KNN(target Point, k int) []Point

type Point

type Point interface {
	// Return the total number of dimensions
	Dim() int
	// Return the value X_{dim}, dim is started from 0
	GetValue(dim int) float64
	// Return the distance between two points
	Distance(p Point) float64
	// Return the distance between the point and the plane X_{dim}=val
	PlaneDistance(val float64, dim int) float64
	// Return timestamp
	GetValues() []float64
	// Return label
	GetLabel() string
	// Return label
	GetGroupLabel() string
	// Return timestamp
	GetTimestamp() int64
	// Return Sequence length one
	GetSequenceLengthOne() int64
	// Return Sequence length two
	GetSequenceLengthTwo() int64
	// Return Sequence dimension one
	GetSequenceDimOne() int64
	// Return Sequence dimension two
	GetSequenceDimTwo() int64
}

type PointBase

type PointBase struct {
	Point
	Vec []float64
}

func NewPointBase

func NewPointBase(vals []float64) PointBase

func (PointBase) Dim

func (b PointBase) Dim() int

func (PointBase) GetGroupLabel

func (b PointBase) GetGroupLabel() string

func (PointBase) GetLabel

func (b PointBase) GetLabel() string

func (PointBase) GetSequenceDimOne

func (b PointBase) GetSequenceDimOne() int64

func (PointBase) GetSequenceDimTwo

func (b PointBase) GetSequenceDimTwo() int64

func (PointBase) GetSequenceLengthOne

func (b PointBase) GetSequenceLengthOne() int64

func (PointBase) GetSequenceLengthTwo

func (b PointBase) GetSequenceLengthTwo() int64

func (PointBase) GetValue

func (b PointBase) GetValue(dim int) float64

func (PointBase) GetValues

func (b PointBase) GetValues() []float64