Count-Min-Sketch Data Structure in TS
npm install count-min-sketch-tscount-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)
``typescript
//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
`
npm install count-min-sketch-ts
npm test
module.exports is a constructor for the data structure, and you import it like so:
`typescript
import { createCountMin, createCountMinSketch } from 'count-min-sketch-ts'
let sketch = createCountMin()
`
* 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 valuehashFunc(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 hashedhashes
+ is an array of k hashes which are required to be pairwise independent.
Returns A count-min sketch data structure
frequency by 1*
key is the item in the table to increment.
$3
Returns the frequency of the item key*
is the item whose frequency we are countingReturns An estimate of the frequency of
key`Note In order for this to be successful both the serialized hash table and the current hash table have to have the same hash functions set.