microspace

README

microspace

Microspace is a spatial index that's optimized for very fast building and nearest-n lookups.

Performance Characteristics

• Inserting n points ultimately runs in O(n log n) time.
• In the worse case, querying for the nearest neighbor runs in O(n) time.
• But in practice it runs much faster. In the benchmark random distribution, querying for nearest neighbors in a set size of 10000 took ~10 nanoseconds longer than querying in a set size of 10.

# Generating a tree with `n` elements:
BenchmarkIndexCreate10                 200000              6010 ns/op
BenchmarkIndexCreate100                 20000             64149 ns/op
BenchmarkIndexCreate1000                 2000            839679 ns/op
BenchmarkIndexCreate10000                 200           8848370 ns/op

# Querying for 3 nearest neighbors in a random set of `n` elements:
BenchmarkIndexNearest10               5000000               294 ns/op
BenchmarkIndexNearest100              5000000               287 ns/op
BenchmarkIndexNearest1000             5000000               286 ns/op
BenchmarkIndexNearest10000            5000000               305 ns/op

# Querying for 3 nearest neighbors in the worst-case set of `n` elements:
BenchmarkIndexNearestWorstCase10      3000000               485 ns/op
BenchmarkIndexNearestWorstCase100      500000              2642 ns/op
BenchmarkIndexNearestWorstCase1000     100000             23939 ns/op
BenchmarkIndexNearestWorstCase10000      5000            240544 ns/op

Documentation

Index

• type Axdex
  • func NewAxdex(capacity uint) *Axdex
  • func (a *Axdex) Insert(p *Point)
  • func (a *Axdex) NearestN(p *Point, n int, max float32) []*Point
  • func (a *Axdex) Points() []*Point
• type Cluster
  • func OPTICS(idx Index, epsilon float32, minPoints int) []*Cluster
• type Index
• type Point
  • func (p *Point) DistanceToSqr(other *Point) float32
  • func (p *Point) String() string

Types

type Axdex

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

func NewAxdex

func NewAxdex(capacity uint) *Axdex

NewAxdex returns a new axis-based index with the provided capacity. It's assumed that you will insert exactly `capacity` points before running queries against the index.

func (*Axdex) Insert

func (a *Axdex) Insert(p *Point)

Insert implements Index.Insert

func (*Axdex) NearestN

func (a *Axdex) NearestN(p *Point, n int, max float32) []*Point

NearestN returns up the `n` nearest neighbors of the point, with a `max` search distance. It's assumed that p is in the index!

func (*Axdex) Points

func (a *Axdex) Points() []*Point

Points implements Index.Points

type Cluster

type Cluster struct {
	Points []*Point
}

func OPTICS

func OPTICS(idx Index, epsilon float32, minPoints int) []*Cluster

OPTICS executes a cluster analysis on the spatial index, where `epsilon` is the max search distance and `minPoints` is the smallest number of individual points needed to qualify as a cluster.

type Index

type Index interface {
	// NearestN returns up the `n` nearest neighbors of the point, with
	// a `max` search distance. `n` May be set to -1 to search for all
	// neighbors in the distance.8
	NearestN(p *Point, n int, max float32) []*Point
	// Points returns all points contained in the spatial index.
	Points() []*Point
}

Index describes a spatial index that can look up a point's nearest neighbors.

type Point

type Point struct{ X, Y float32 }

Point represents a point in two-dimensional space.

func (*Point) DistanceToSqr

func (p *Point) DistanceToSqr(other *Point) float32

DistanceToSqr returns the squared distance to the `other` point.

func (*Point) String

func (p *Point) String() string

String returns a textual representation of the point.