xor

Documentation

Overview

Package xor implements a nearest-neighbor data structure for the XOR-metric.

Index

• Variables
• func Proximity(x, y Point) int
• type Key
  • func ChooseKey() Key
  • func Combine(keys ...Key) Key
  • func HashBytes(b []byte) Key
  • func HashInt64(i int64) Key
  • func HashString(s string) Key
  • func (id Key) Bit(k int) int
  • func (id Key) Key() Key
  • func (id Key) ShortString(k uint) string
  • func (id Key) String() string
• type Metric
  • func (m *Metric) Add(item Point) (level int, err error)
  • func (m *Metric) ChooseMinK(k int) Key
  • func (m *Metric) Clear()
  • func (m *Metric) Copy() *Metric
  • func (m *Metric) Dump() []Point
  • func (m *Metric) Iterate(f func(Point))
  • func (m *Metric) Nearest(pivot Key, k int) []Point
  • func (m *Metric) Remove(id Key) Point
  • func (m *Metric) Size() int
• type Point

Variables

var ErrDup = errors.New("duplicate point")

Functions

func Proximity

func Proximity(x, y Point) int

Proximity equals the number of contiguous bits, starting from the metrically most significant one, that x and y share.

Types

type Key

type Key uint64

Key represents a point in the 64-bit XOR-space.

func ChooseKey

func ChooseKey() Key

func Combine

func Combine(keys ...Key) Key

func HashBytes

func HashBytes(b []byte) Key

func HashInt64

func HashInt64(i int64) Key

func HashString

func HashString(s string) Key

func (Key) Bit

func (id Key) Bit(k int) int

Bit returns the k-th bit from metric point of view. The zero-th bit is most significant.

func (Key) Key

func (id Key) Key() Key

Key implements interface Point

func (Key) ShortString

func (id Key) ShortString(k uint) string

String returns a textual representation of the id, truncated to the k MSBs.

func (Key) String

func (id Key) String() string

String returns a textual representation of the id

type Metric

type Metric struct {
	Point
	// contains filtered or unexported fields
}

Metric is an XOR-metric space that supports point addition and nearest neighbor (NN) queries. The zero value is an empty metric space.

func (*Metric) Add

func (m *Metric) Add(item Point) (level int, err error)

Add adds the item to the metric. It returns the smallest number of significant bits that distinguish this item from the rest in the metric.

func (*Metric) ChooseMinK

func (m *Metric) ChooseMinK(k int) Key

ChooseMinK chooses k random keys and returns the one which, if inserted into the metric, would result in the shallowest position in the XOR tree. In other words, it returns the most balanced choice. We recommend k equals 7.

func (*Metric) Clear

func (m *Metric) Clear()

Clear removes all points from the metric

func (*Metric) Copy

func (m *Metric) Copy() *Metric

Copy returns a deep copy of the metric

func (*Metric) Dump

func (m *Metric) Dump() []Point

func (*Metric) Iterate

func (m *Metric) Iterate(f func(Point))

Iterate calls f on each node of the XOR-tree that has a non-nil item.

func (*Metric) Nearest

func (m *Metric) Nearest(pivot Key, k int) []Point

Nearest returns the k points in the metric that are closest to the pivot.

func (*Metric) Remove

func (m *Metric) Remove(id Key) Point

Remove removes an item with id from the metric, if present. It returns the removed item, or nil if non present.

func (*Metric) Size

func (m *Metric) Size() int

Size returns the number of points in the metric

type Point

type Point interface {
	Key() Key
}

Point is any type that has an XOR-space Key