base/bif/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.

Bf

The Bloom filter handle.

X

The element to add.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge, bloomfilter_decrement

bloomfilter_basic_init
Type

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

Creates a basic Bloom filter.

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.

See also: bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_add, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge, global_hash_seed

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.

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.

See also: bloomfilter_basic_init, bloomfilter_counting_init, bloomfilter_add, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge, global_hash_seed

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.

Bf

The Bloom filter handle.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_add, bloomfilter_lookup, bloomfilter_merge

bloomfilter_counting_init
Type

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

Creates a counting Bloom filter.

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 appropiate 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.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_add, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge, global_hash_seed

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.

Bf

The coubting bloom filter handle.

X

The element to decrement

Returns

True on success

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge

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.

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.

Bf1

The first Bloom filter handle.

Bf2

The second Bloom filter handle.

Returns

The intersection of bf1 and bf2.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_add, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge

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.

Bf

The Bloom filter handle.

X

The element to count.

Returns

the counter associated with x in bf.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_add, bloomfilter_clear, bloomfilter_merge

bloomfilter_merge
Type

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

Merges two Bloom filters.

Bf1

The first Bloom filter handle.

Bf2

The second Bloom filter handle.

Returns

The union of bf1 and bf2.

See also: bloomfilter_basic_init, bloomfilter_basic_init2, bloomfilter_counting_init, bloomfilter_add, bloomfilter_lookup, bloomfilter_clear, bloomfilter_merge