Skip to main content

countminsketch.go

countminsketch.go - Overview​

This file implements the Count-Min Sketch data structure for approximating event frequencies in data streams. It includes functionalities for initializing, updating, querying, merging, serializing, and deserializing Count-Min Sketches.

Detailed Documentation​

CountMinSketchOpts​

type CountMinSketchOpts struct {
	depth  uint64      // depth of the count min sketch matrix
	width  uint64      // width of the count min sketch matrix
	hasher hash.Hash64 // the hash function used to hash the key
}
  • Purpose: Stores the options for creating a Count-Min Sketch, including the depth and width of the matrix and the hash function.
    • depth: Depth of the Count-Min Sketch matrix.
    • width: Width of the Count-Min Sketch matrix.
    • hasher: The hash function used to hash the key.

CountMinSketch​

type CountMinSketch struct {
	opts *CountMinSketchOpts

	matrix [][]uint64 // the underlying matrix that stores the counts
	count  uint64     // total number of occurrences seen by the sketch
}
  • Purpose: Implements the Count-Min Sketch data structure.
    • opts: Options for the Count-Min Sketch.
    • matrix: The underlying matrix that stores the counts.
    • count: Total number of occurrences seen by the sketch.

newCountMinSketchOpts​

func newCountMinSketchOpts(args []string) (*CountMinSketchOpts, error)
  • Purpose: Extracts the depth and width of the matrix from the input arguments.
  • Parameters:
    • args: A string slice containing the width and depth as strings.
  • Returns:
    • *CountMinSketchOpts: A pointer to a CountMinSketchOpts struct containing the parsed width and depth.
    • error: An error if parsing fails or if width/depth are not positive integers.

newCountMinSketchOptsWithErrorRate​

func newCountMinSketchOptsWithErrorRate(args []string) (*CountMinSketchOpts, error)
  • Purpose: Calculates the depth and width of the matrix based on the given error rate (ε) and probability (δ).
  • Parameters:
    • args: A string slice containing the error rate and probability as strings.
  • Returns:
    • *CountMinSketchOpts: A pointer to a CountMinSketchOpts struct containing the calculated width and depth.
    • error: An error if parsing fails or if error rate/probability are not within (0, 1).

newCountMinSketch​

func newCountMinSketch(opts *CountMinSketchOpts) *CountMinSketch
  • Purpose: Creates a new Count-Min Sketch with the given options and initializes the underlying matrix.
  • Parameters:
    • opts: A pointer to a CountMinSketchOpts struct containing the options for the sketch.
  • Returns:
    • *CountMinSketch: A pointer to the newly created CountMinSketch.

(*CountMinSketch).info​

func (c *CountMinSketch) info() []interface{}
  • Purpose: Returns information about the underlying matrix for the given Count-Min Sketch.
  • Parameters:
    • c: A pointer to a CountMinSketch struct.
  • Returns:
    • []interface{}: A slice of interfaces containing the width, depth, and count of the sketch.

(*CountMinSketch).baseHashes​

func (c *CountMinSketch) baseHashes(key []byte) (hash1, hash2 uint32)
  • Purpose: Computes the base hash values which are then used to generate other hash values for the given key.
  • Parameters:
    • key: The key as a byte slice.
  • Returns:
    • hash1: The first hash value as a uint32.
    • hash2: The second hash value as a uint32.

(*CountMinSketch).matrixPositions​

func (c *CountMinSketch) matrixPositions(key []byte) (positions []uint64)
  • Purpose: Returns the positions in the matrix where the count of the given key should be updated.
  • Parameters:
    • key: The key as a byte slice.
  • Returns:
    • positions: A slice of uint64 representing the positions in the matrix.

(*CountMinSketch).updateMatrix​

func (c *CountMinSketch) updateMatrix(key string, count uint64)
  • Purpose: Updates the underlying matrix for the given key by count.
  • Parameters:
    • key: The key as a string.
    • count: The amount to increment the count by.

(*CountMinSketch).estimateCount​

func (c *CountMinSketch) estimateCount(key string) uint64
  • Purpose: Estimates the count of a key in the sketch.
  • Parameters:
    • key: The key as a string.
  • Returns:
    • uint64: The estimated count of the key.

(*CountMinSketch).DeepCopy​

func (c *CountMinSketch) DeepCopy() *CountMinSketch
  • Purpose: Returns a deep copy of the Count-Min Sketch.
  • Parameters:
    • c: A pointer to a CountMinSketch struct.
  • Returns:
    • *CountMinSketch: A pointer to the deep copy of the CountMinSketch.

(*CountMinSketch).mergeMatrices​

func (c *CountMinSketch) mergeMatrices(sources []*CountMinSketch, weights []uint64, originalKey string, keys []string)
  • Purpose: Combines two or more Count-Min Sketches and puts the result in another Count-Min Sketch.
  • Parameters:
    • sources: A slice of pointers to CountMinSketch structs to be merged.
    • weights: A slice of uint64 representing the weights for each source sketch.
    • originalKey: The key of the destination CountMinSketch.
    • keys: A slice of keys corresponding to the source sketches.

(*CountMinSketch).serialize​

func (c *CountMinSketch) serialize(buffer *bytes.Buffer) error
  • Purpose: Encodes the CountMinSketch into a byte slice.
  • Parameters:
    • buffer: A pointer to a bytes.Buffer to write the serialized data to.
  • Returns:
    • error: An error if serialization fails.

DeserializeCMS​

func DeserializeCMS(buffer *bytes.Reader) (*CountMinSketch, error)
  • Purpose: Reconstructs a CountMinSketch from a byte slice.
  • Parameters:
    • buffer: A pointer to a bytes.Reader to read the serialized data from.
  • Returns:
    • *CountMinSketch: A pointer to the reconstructed CountMinSketch.
    • error: An error if deserialization fails.

evalCMSMerge​

func evalCMSMerge(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Merges multiple sketches into one.
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.merge command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

evalCMSQuery​

func evalCMSQuery(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Returns the count for one or more items in a sketch.
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.query command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

evalCMSIncrBy​

func evalCMSIncrBy(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Increases the count of item by increment.
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.incrby command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

evalCMSINFO​

func evalCMSINFO(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Returns width, depth and total count of the sketch.
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.info command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

evalCMSINITBYDIM​

func evalCMSINITBYDIM(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Initializes a Count-Min Sketch by dimensions (width and depth).
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.initbydim command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

evalCMSINITBYPROB​

func evalCMSINITBYPROB(args []string, store *dstore.Store) *EvalResponse
  • Purpose: Initializes a Count-Min Sketch for a given error rate and probability.
  • Parameters:
    • args: A slice of strings representing the arguments to the cms.initbyprob command.
    • store: A pointer to a dstore.Store for retrieving and storing data.
  • Returns:
    • *EvalResponse: An EvalResponse struct containing the result and any error.

createCountMinSketch​

func createCountMinSketch(key string, opts *CountMinSketchOpts, store *dstore.Store) error
  • Purpose: Creates a new Count-Min Sketch in the key-value store.
  • Parameters:
    • key: The key to store the sketch under.
    • opts: Options for the Count-Min Sketch.
    • store: A pointer to a dstore.Store for storing the sketch.
  • Returns:
    • error: An error if the key already exists.

getCountMinSketch​

func getCountMinSketch(key string, store *dstore.Store) (*CountMinSketch, error)
  • Purpose: Fetches the Count-Min Sketch for the given key from the key-value store.
  • Parameters:
    • key: The key to retrieve the sketch from.
    • store: A pointer to a dstore.Store for retrieving the sketch.
  • Returns:
    • *CountMinSketch: A pointer to the retrieved CountMinSketch.
    • error: An error if the key does not exist or has the wrong encoding.

Code Examples​

Not applicable; the code is self-explanatory.

Getting Started Relevance​