FrequencySketch
Classes
- FrequencySketch
A probabilistic multiset for estimating the popularity of an element within a time window. The maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically halves the popularity of all elements.
This class maintains a 4-bit CountMinSketch [1] with periodic aging to provide the popularity history for the TinyLfu admission policy [2]. The time and space efficiency of the sketch allows it to cheaply estimate the frequency of an entry in a stream of cache access events.
The counter matrix is represented as a single dimensional array holding 16 counters per slot. A fixed depth of four balances the accuracy and cost, resulting in a width of four times the length of the array. To retain an accurate estimation the array's length equals the maximum number of entries in the cache, increased to the closest power-of-two to exploit more efficient bit masking. This configuration results in a confidence of 93.75% and error bound of e / width.
The frequency of all entries is aged periodically using a sampling window based on the maximum number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps the sketch fresh by dividing all counters by two and subtracting based on the number of odd counters found. The O(n) cost of aging is amortized, ideal for hardware prefetching, and uses inexpensive bit manipulations per array location.
[1] An Improved Data Stream Summary: The Count-Min Sketch and its Applicationshttp://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf[2] TinyLFU: A Highly Efficient Cache Admission Policyhttps://dl.acm.org/citation.cfm?id=3149371
NOTE: ported from "caffeine"
Constants
- MAX_INT_32 :
number Maximum value of a signed 32bit integer
FrequencySketch
A probabilistic multiset for estimating the popularity of an element within a time window. The maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically halves the popularity of all elements.
This class maintains a 4-bit CountMinSketch [1] with periodic aging to provide the popularity history for the TinyLfu admission policy [2]. The time and space efficiency of the sketch allows it to cheaply estimate the frequency of an entry in a stream of cache access events.
The counter matrix is represented as a single dimensional array holding 16 counters per slot. A fixed depth of four balances the accuracy and cost, resulting in a width of four times the length of the array. To retain an accurate estimation the array's length equals the maximum number of entries in the cache, increased to the closest power-of-two to exploit more efficient bit masking. This configuration results in a confidence of 93.75% and error bound of e / width.
The frequency of all entries is aged periodically using a sampling window based on the maximum number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps the sketch fresh by dividing all counters by two and subtracting based on the number of odd counters found. The O(n) cost of aging is amortized, ideal for hardware prefetching, and uses inexpensive bit manipulations per array location.
[1] An Improved Data Stream Summary: The Count-Min Sketch and its Applications http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf [2] TinyLFU: A Highly Efficient Cache Admission Policy https://dl.acm.org/citation.cfm?id=3149371
NOTE: ported from "caffeine"
Kind: global class
See: https://github.com/ben-manes/caffeine/blob/master/caffeine/src/main/java/com/github/benmanes/caffeine/cache/FrequencySketch.java
Author: ben.manes@gmail.com (Ben Manes)
Author: Alex Goldring 2021/04/08
- FrequencySketch
- .sampleSize :
number - .tableMask :
number - .table :
Uint32Array|null - .size :
number - .ensureCapacity(maximumSize)
- .isNotInitialized() ⇒
boolean - .frequency(input_hash) ⇒
number - .increment(input_hash)
- .incrementAt(i, j) ⇒
boolean - .reset()
- .indexOf(item, i) ⇒
number - .spread(v) ⇒
number
- .sampleSize :
frequencySketch.sampleSize : number
Kind: instance property of FrequencySketch
frequencySketch.tableMask : number
Kind: instance property of FrequencySketch
frequencySketch.table : Uint32Array | null
Kind: instance property of FrequencySketch
frequencySketch.size : number
Kind: instance property of FrequencySketch
frequencySketch.ensureCapacity(maximumSize)
Initializes and increases the capacity of this FrequencySketch instance, if necessary, to ensure that it can accurately estimate the popularity of elements given the maximum size of the cache. This operation forgets all previous counts when resizing.
Kind: instance method of FrequencySketch
| Param | Type | Description |
|---|---|---|
| maximumSize | number | the maximum size of the cache |
frequencySketch.isNotInitialized() ⇒ boolean
Returns if the sketch has not yet been initialized, requiring that #ensureCapacity is called before it begins to track frequencies.
Kind: instance method of FrequencySketch
frequencySketch.frequency(input_hash) ⇒ number
Returns the estimated number of occurrences of an element, up to the maximum (15).
Kind: instance method of FrequencySketch
Returns: number - the estimated number of occurrences of the element; possibly zero but never negative
| Param | Type | Description |
|---|---|---|
| input_hash | number | the element to count occurrences of |
frequencySketch.increment(input_hash)
Increments the popularity of the element if it does not exceed the maximum (15). The popularity of all elements will be periodically down sampled when the observed events exceeds a threshold. This process provides a frequency aging to allow expired long term entries to fade away.
Kind: instance method of FrequencySketch
| Param | Type | Description |
|---|---|---|
| input_hash | number | the element to add |
frequencySketch.incrementAt(i, j) ⇒ boolean
Increments the specified counter by 1 if it is not already at the maximum value (15).
Kind: instance method of FrequencySketch
Returns: boolean - if incremented
| Param | Type | Description |
|---|---|---|
| i | number | the table index (8 counters) |
| j | number | the counter to increment |
frequencySketch.reset()
Reduces every counter by half of its original value.
Kind: instance method of FrequencySketch
frequencySketch.indexOf(item, i) ⇒ number
Returns the table index for the counter at the specified depth.
Kind: instance method of FrequencySketch
Returns: number - the table index
| Param | Type | Description |
|---|---|---|
| item | number | the element's hash |
| i | number | the counter depth |
frequencySketch.spread(v) ⇒ number
Applies a supplemental hash function to a given hashCode, which defends against poor quality
Kind: instance method of FrequencySketch
| Param | Type |
|---|---|
| v | number |
MAX_INT_32 : number
Maximum value of a signed 32bit integer
Kind: global constant