pgm

README

PGM-index

A Go implementation of the PGM index

What is a PGM index?

Website | Paper

The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes while providing the same worst-case query time guarantees.

Paolo Ferragina and Giorgio Vinciguerra. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. PVLDB, 13(8): 1162-1175, 2020.

Credit

• The Rotating Calipers algorithm is ported from https://github.com/bkiers/RotatingCalipers. Complete credit goes to its author.
• The Monotone Chain algorithm for the convex hull is from https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain.

Documentation

Index

• type ApproxPos
• type Index
  • func NewIndex(input []float64, epsilon int) *Index
  • func (ind *Index) Search(k float64) (ApproxPos, error)
• type Segment

Types

type ApproxPos

type ApproxPos struct {
	Pos int
	Lo  int
	Hi  int
}

type Index

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

Index contains the PGM index. It is just a hierarchy of segments.

func NewIndex

func NewIndex(input []float64, epsilon int) *Index

NewIndex returns a new static PGM index.

func (*Index) Search

func (ind *Index) Search(k float64) (ApproxPos, error)

type Segment

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

Segment contains the slope and intercept of the line segment and the corresponding key.