base/bif/bloom-filter.bif.zeek
- GLOBAL
Functions to create and manipulate Bloom filters.
- Namespace:
GLOBAL
Summary
Functions
Adds an element to a Bloom filter. |
|
Creates a basic Bloom filter. |
|
Creates a basic Bloom filter. |
|
Removes all elements from a Bloom filter. |
|
Creates a counting Bloom filter. |
|
Decrements the counter for an element that was added to a counting bloom filter in the past. |
|
Returns a string with a representation of a Bloom filter’s internal state. |
|
Intersects two Bloom filters. |
|
Retrieves the counter for a given element in a Bloom filter. |
|
Merges two Bloom filters. |
Detailed Interface
Functions
- bloomfilter_add
-
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 withbloomfilter_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 withbloomfilter_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
-
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 withbloomfilter_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
-
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
-
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
-
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
-
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
-
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