topk

package module

v0.0.0-...-7c60bef Latest Latest Go to latest Published: Jul 3, 2023 License: 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/liuzl/topk

Links

Open Source Insights

README ¶

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
	Items []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) InsertTokens ¶

func (s *Stream) InsertTokens(tokens []string, count int) Element

InsertTokens 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