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.

Parameters
  • 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.

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.

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.

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.

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.

Parameters

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.

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.

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.

Parameters
  • bf – The counting 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.

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.

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.

Parameters
  • 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.

Parameters
  • 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