topk

package

v1.0.1 Latest Latest Go to latest Published: Nov 20, 2019 License: Apache-2.0, MIT Imports: 6 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/riking/go-prometheus-topk

Links

Open Source Insights

Documentation ¶

Overview ¶

Package topk implements the Filtered Space-Saving TopK streaming algorithm

The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf

The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf

This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table.

Licensed under the MIT license.

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type Element ¶

type Element struct {
	Key   string
	Count float64
	Error float64
}

Element is a TopK item

type Stream ¶

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

Stream calculates the TopK elements for a stream.

This type has been modified from the original; it has been changed to use floating-point counters.

func NewStream ¶

func NewStream(n int) *Stream

NewStream returns a Stream estimating the top n most frequent elements

func (*Stream) Estimate ¶

func (s *Stream) Estimate(x string) Element

Estimate returns an estimate for the item x

func (*Stream) GobDecode ¶

func (s *Stream) GobDecode(b []byte) error

func (*Stream) GobEncode ¶

func (s *Stream) GobEncode() ([]byte, error)

func (*Stream) Insert ¶

func (s *Stream) Insert(x string, count float64) Element

Insert adds an element to the stream to be tracked It returns an estimation for the just inserted element

func (*Stream) Keys ¶

func (s *Stream) Keys() []Element

Keys returns the current estimates for the most frequent elements

Source Files ¶

View all Source files

topk.go

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