Count-min-sketch-ts NPM

count-min-sketch-ts

Depends on Jest, required Node 18+

The TypeScript implementation of Coromode and Muthukrishnan's Count-Min sketch data structure for JavaScript. The count-min sketch is basically a high powered generalization of the bloom filter. While a bloom filter gives an efficient way to approximate membership of a set, a count-min sketch can give approximate data about the relative frequency of items in the set.

For more information see the following references:

Count-Min sketch: https://sites.google.com/site/countminsketch/
next big thing syndrome: http://lkozma.net/blog/sketching-data-structures/
G. Cormode, S. Muthukrishnan. "Approximating Data with the Count-Min Data Structure". IEEE Trans. on Software (2012)

Example

//Import data structures
import { createCountMin, createCountMinSketch } from 'count-min-sketch-ts'

//Import hash functions
import { JSHash, SDBMHash, DJBHash, DEKHash, APHash, wrapperHashFunction } from 'count-min-sketch-ts'

//Create data structure, with default 28 width, 10 depth and single hash ('k-hash') function used
let sketch = createCountMin()

//Create customizable implementation with user-defined width, depth and set of hash functions (each raw in table calculated with different hash function)
let sketch = createCountMinSketch(10, 6, wrapperHashFunction([APHash, JSHash, SDBMHash, DJBHash, DEKHash]))

//Increment counters
sketch.update("foo")
sketch.update(1515)
sketch.update(1515)

let obj= {test: "test", key: 123}
sketch.update(obj)

//Query results
console.log(sketch.query(1515))  //Prints 2
console.log(sketch.query(obj))   //Prints 1
console.log(sketch.query("bar")) //Prints 0

Install

npm install count-min-sketch-ts

Test (Jest)

npm test

API

module.exports is a constructor for the data structure, and you import it like so:

import { createCountMin, createCountMinSketch } from 'count-min-sketch-ts'

let sketch = createCountMin()

`let sketch = createCountMin(epsilon, probError[, hashFunc])`

Creates a count-min sketch data structure.

epsilon is the accuracy of the data structure (ie the size of bins that we are computing frequencies of)
probError is the probability of incorrectly computing a value
hashFunc(key, hashes) is a hash function for the data structure. (optional) the parameters to this function are as follows:
- key is the item that is being hashed
- hashes is an array of k hashes which are required to be pairwise independent.

Returns A count-min sketch data structure