topk

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.

Index

• type Element
• type Stream
  • func New(n int) *Stream
  • func (s *Stream) Estimate(x string) Element
  • func (s *Stream) GobDecode(b []byte) error
  • func (s *Stream) GobEncode() ([]byte, error)
  • func (s *Stream) Insert(x string, count int64) Element
  • func (s *Stream) Keys() []Element

Types

type Element

type Element struct {
	Key   string
	Count int64
	Error int64
}

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 int64) 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