topk

package module

v0.0.0-...-593b4f2 Latest Latest Go to latest Published: Nov 19, 2019 License: MIT Imports: 5 Imported by: 9

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/dgryski/go-topk

Links

Open Source Insights

README ¶

go-topk: "filtered space saving" streaming topk algorithm

godoc: http://godoc.org/github.com/dgryski/go-topk

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 int
	Error int
}

Element is a TopK item

type Stream ¶

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

Stream calculates the TopK elements for a stream

func New ¶

func New(n int) *Stream

New 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 int) 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

Directories ¶

Path	Synopsis
cmd
topk-fss

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