Bloom filter in Aleph-w (probabilistic set membership, false positives, and tuning). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <tclap/CmdLine.h>
#include <bloom-filter.H>

Include dependency graph for bloom_filter_example.C:

Functions
void	print_section (const string &title)

void	print_subsection (const string &title)

void	demo_basic ()

void	demo_false_positives ()

void	demo_optimal_params ()

void	demo_spell_checker ()

void	demo_cache_filter ()

void	demo_space_comparison ()

int	main (int argc, char *argv[])

Detailed Description

Bloom filter in Aleph-w (probabilistic set membership, false positives, and tuning).

Overview

This example demonstrates Aleph-w's Bloom_Filter<T>: a probabilistic data structure for set membership queries.

If it says **"not present"**: the element is definitely not in the set.
If it says **"present"**: the element is probably in the set (false positives are possible).

The program is structured as a set of independent demos:

basic insert/query usage
observed false positives
parameter tuning and sizing intuition
spell-check / cache-filter style examples
space comparison vs storing elements

Data model used by this example

Bloom filter type: Bloom_Filter<string>
Parameters:
- m: bit array size
- k: number of hash functions

Usage / CLI

This example uses TCLAP and a selector:

--section / -s <section>: run only one section. Valid values: basic, fp, params, spell, cache, space, all (default).
--help: show help.

# Run all demos
./bloom_filter_example
 
# Run a specific section
./bloom_filter_example --section basic
./bloom_filter_example --section fp
./bloom_filter_example --section params
./bloom_filter_example --section spell
./bloom_filter_example --section cache
./bloom_filter_example --section space
 
# Short form
./bloom_filter_example -s space
 
# Show help
./bloom_filter_example --help

Complexity

Let k be the number of hash functions.

insert: O(k)
query: O(k)
space: O(m) bits

Pitfalls and edge cases

Standard Bloom filters do not support deletion (use a counting variant).
Poor parameter choices (too small m, too large/small k) increase the false positive rate.