bloom-filter.bif.zeek

GLOBAL

Functions to create and manipulate Bloom filters.

Namespace: GLOBAL

Summary

Functions

`bloomfilter_add`: `function`	Adds an element to a Bloom filter.
`bloomfilter_basic_init`: `function`	Creates a basic Bloom filter.
`bloomfilter_basic_init2`: `function`	Creates a basic Bloom filter.
`bloomfilter_clear`: `function`	Removes all elements from a Bloom filter.
`bloomfilter_counting_init`: `function`	Creates a counting Bloom filter.
`bloomfilter_decrement`: `function`	Decrements the counter for an element that was added to a counting bloom filter in the past.
`bloomfilter_internal_state`: `function`	Returns a string with a representation of a Bloom filter’s internal state.
`bloomfilter_intersect`: `function`	Intersects two Bloom filters.
`bloomfilter_lookup`: `function`	Retrieves the counter for a given element in a Bloom filter.
`bloomfilter_merge`: `function`	Merges two Bloom filters.

Detailed Interface

Functions

bloomfilter_add

Type: function (bf: opaque of bloomfilter, x: any) : any

Adds an element to a Bloom filter. For counting bloom filters, the counter is incremented.

Parameters

bf – The Bloom filter handle.
x – The element to add.

bloomfilter_basic_init

Type: function (fp: double, capacity: count, name: string &default = "" &optional) : opaque of bloomfilter

Creates a basic Bloom filter.

Parameters

fp – The desired false-positive rate.
capacity – the maximum number of elements that guarantees a false-positive rate of fp.
name – A name that uniquely identifies and seeds the Bloom filter. If empty, the filter will use global_hash_seed if that’s set, and otherwise use a local seed tied to the current Zeek process. Only filters with the same seed can be merged with bloomfilter_merge.

Returns

A Bloom filter handle.

bloomfilter_basic_init2

Type: function (k: count, cells: count, name: string &default = "" &optional) : opaque of bloomfilter

Creates a basic Bloom filter. This function serves as a low-level alternative to bloomfilter_basic_init where the user has full control over the number of hash functions and cells in the underlying bit vector.

Parameters

k – The number of hash functions to use.
cells – The number of cells of the underlying bit vector.
name – A name that uniquely identifies and seeds the Bloom filter. If empty, the filter will use global_hash_seed if that’s set, and otherwise use a local seed tied to the current Zeek process. Only filters with the same seed can be merged with bloomfilter_merge.

Returns

A Bloom filter handle.

bloomfilter_clear

Type: function (bf: opaque of bloomfilter) : any

Removes all elements from a Bloom filter. This function resets all bits in the underlying bitvector back to 0 but does not change the parameterization of the Bloom filter, such as the element type and the hasher seed.

Parameters: bf – The Bloom filter handle.

bloomfilter_counting_init

Type: function (k: count, cells: count, max: count, name: string &default = "" &optional) : opaque of bloomfilter

Creates a counting Bloom filter.

Parameters

k – The number of hash functions to use.
cells – The number of cells of the underlying counter vector. As there’s no single answer to what’s the best parameterization for a counting Bloom filter, we refer to the Bloom filter literature here for choosing an appropriate value.
max – The maximum counter value associated with each element described by w = ceil(log_2(max)) bits. Each bit in the underlying counter vector becomes a cell of size w bits.
name – A name that uniquely identifies and seeds the Bloom filter. If empty, the filter will use global_hash_seed if that’s set, and otherwise use a local seed tied to the current Zeek process. Only filters with the same seed can be merged with bloomfilter_merge.

Returns

A Bloom filter handle.

bloomfilter_decrement

Type: function (bf: opaque of bloomfilter, x: any) : bool

Decrements the counter for an element that was added to a counting bloom filter in the past.

Note that decrement operations can lead to false negatives if used on a counting bloom-filter that exceeded the width of its counter.

Parameters

bf – The counting bloom filter handle.
x – The element to decrement

Returns

True on success

bloomfilter_internal_state

Type: function (bf: opaque of bloomfilter) : string

Returns a string with a representation of a Bloom filter’s internal state. This is for debugging/testing purposes only.

Parameters: bf – The Bloom filter handle.
Returns: a string with a representation of a Bloom filter’s internal state.

bloomfilter_intersect

Type: function (bf1: opaque of bloomfilter, bf2: opaque of bloomfilter) : opaque of bloomfilter

Intersects two Bloom filters.

The resulting Bloom filter returns true when queried for elements that were contained in both bloom filters. Note that intersected Bloom filters have a slightly higher probability of false positives than Bloom filters created from scratch.

Please note that, while this function works with basic and with counting bloom filters, the result always is a basic bloom filter. So - intersecting two counting bloom filters will result in a basic bloom filter. The reason for this is that there is no reasonable definition of how to handle counters during intersection.

Parameters

bf1 – The first Bloom filter handle.
bf2 – The second Bloom filter handle.

Returns

The intersection of bf1 and bf2.

bloomfilter_lookup

Type: function (bf: opaque of bloomfilter, x: any) : count

Retrieves the counter for a given element in a Bloom filter.

For a basic bloom filter, this is 0 when the element is not part of the bloom filter, or 1 if it is part of the bloom filter.

For a counting bloom filter, this is the estimate of how often an element was added.

Parameters

bf – The Bloom filter handle.
x – The element to count.

Returns

the counter associated with x in bf.

bloomfilter_merge

Type: function (bf1: opaque of bloomfilter, bf2: opaque of bloomfilter) : opaque of bloomfilter

Merges two Bloom filters.

Parameters

bf1 – The first Bloom filter handle.
bf2 – The second Bloom filter handle.

Returns

The union of bf1 and bf2.