1. Understand “possibly present”
A probabilistic membership filter stores a compact hashed representation rather than an exact set of keys. CoolBox's EGH implementation hashes each value into several prime-sized boolean layers. Inserting sets one bucket in every layer; querying checks all corresponding buckets.
False means absent; true means possibly present. A positive can be caused by collisions with other keys. Confirm positives against an authoritative set or database. Inserted values should never return false while the filter remains intact, has not been cleared, and uses the same key representation.
This makes a filter useful for avoiding unnecessary database or cache reads. It is not suitable by itself for authorization, exact duplicate rejection, or deciding to discard data: a false positive could otherwise lose a legitimate item.
2. Size for the expected workload
Allocate for 1,000 expected insertions and a 0.01 target false-positive rate. Insert IDs 0 through 999, then query the disjoint range 100,000 through 109,999. Every positive in that second range is a known false positive.
The target is a sizing input, not a guaranteed measured rate. The occupancy-based estimate and the empirical rate on 10,000 probes answer different questions. Inserting far more keys than planned saturates the layers and increases false positives.
3. Insert and measure
Follow the matching installation guide. Use signed 64-bit integer keys for comparable examples across the bindings. The programs verify all inserted keys, count false positives on absent keys, report occupancy estimates, and clear the filter.
No Python EGH filter binding was found in the current package. Use Go, Rust, or native C++ for this example; do not substitute Python's exact set and call it an EGH filter. Check the Python binding source for updates.
package main
import (
"fmt"
"log"
coolbox "github.com/MeanderingAI/CoolBox/_deliverables/libraries/bindings/go_bindings"
)
func run() error {
filter, err := coolbox.NewInt64Filter(coolbox.EGHFilterKind, 1000, 0.01)
if err != nil { return err }
defer filter.Close()
for id := int64(0); id < 1000; id++ {
if err := filter.Insert(id); err != nil { return err }
}
for id := int64(0); id < 1000; id++ {
present, err := filter.Contains(id)
if err != nil { return err }
if !present { return fmt.Errorf("false negative for %d", id) }
}
falsePositives := 0
for id := int64(100000); id < 110000; id++ {
present, err := filter.Contains(id)
if err != nil { return err }
if present { falsePositives++ }
}
estimated, err := filter.EstimatedFalsePositiveRate()
if err != nil { return err }
calls, err := filter.InsertCount()
if err != nil { return err }
approximate, err := filter.ApproximateCount()
if err != nil { return err }
fmt.Printf("Insert calls: %d; approximate count: %d\n", calls, approximate)
fmt.Printf("False positives: %d/10000; empirical: %.4f; estimated: %.4f\n",
falsePositives, float64(falsePositives)/10000, estimated)
if err := filter.Clear(); err != nil { return err }
present, err := filter.Contains(42)
if err != nil { return err }
if present { return fmt.Errorf("filter was not cleared") }
return nil
}
func main() {
if err := run(); err != nil { log.Fatal(err) }
}use coolbox_rs::{Int64ProbabilisticFilter, ProbabilisticFilterKind};
fn main() -> Result<(), String> {
let mut filter = Int64ProbabilisticFilter::new(
ProbabilisticFilterKind::Egh, 1000, 0.01,
)?;
for id in 0_i64..1000 { filter.insert(id)?; }
for id in 0_i64..1000 {
if !filter.contains(id) {
return Err(format!("false negative for {id}"));
}
}
let false_positives = (100000_i64..110000)
.filter(|id| filter.contains(*id)).count();
println!("Insert calls: {}; approximate count: {}",
filter.insert_count(), filter.approximate_count());
println!("False positives: {false_positives}/10000; empirical: {:.4}; estimated: {:.4}",
false_positives as f64 / 10000.0, filter.estimated_false_positive_rate());
filter.clear()?;
if filter.contains(42) { return Err("filter was not cleared".into()); }
Ok(())
}#include <cstdint>
#include <exception>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <egh_filter.h>
int main() {
try {
data_structures::EGHFilter<std::int64_t> filter(1000, 0.01);
for (std::int64_t id = 0; id < 1000; ++id) filter.insert(id);
for (std::int64_t id = 0; id < 1000; ++id) {
if (!filter.contains(id)) throw std::runtime_error("False negative");
}
int false_positives = 0;
for (std::int64_t id = 100000; id < 110000; ++id) {
if (filter.contains(id)) ++false_positives;
}
std::cout << "Insert calls: " << filter.insert_count()
<< "; approximate count: " << filter.approximate_count()
<< "\nFalse positives: " << false_positives << "/10000"
<< std::fixed << std::setprecision(4)
<< "; empirical: " << false_positives / 10000.0
<< "; estimated: " << filter.estimated_false_positive_rate()
<< '\n';
filter.clear();
if (filter.contains(42)) throw std::runtime_error("Filter was not cleared");
return 0;
} catch (const std::exception& error) {
std::cerr << error.what() << '\n';
return 1;
}
}The native template is in DATASTRUCTURE/filters/headers/egh_filter.h. Link the installed CoolBox::data_structures target to inherit include directories, or add the filter header directory while preserving its neighboring source-tree hash headers.
4. Read the counters correctly
In the native C++ run of this exact example, all 1,000 inserted IDs were found, and 89 of 10,000 absent IDs returned positive: an empirical rate of 0.89%. The occupancy estimate rounded to 0.87%, and the approximate count was 1,000. Clearing the filter also passed its check. These are measured example results, not required outputs on every platform.
insert_count counts insertion calls, including duplicates. It is not exact distinct cardinality. approximate_count estimates cardinality from occupied buckets, while estimated_false_positive_rate multiplies layer occupancies; neither is a guarantee.
The empirical rate is false positives / 10,000 because all probe IDs are known absent. Verify zero false negatives separately on the inserted range. A measured rate will depend on the tested keys and implementation; do not require it to equal the configured 1% target exactly.
clear resets every layer and the insertion counter. This API does not expose per-item removal. Do not clear a bucket yourself: different keys can share it, so doing so could introduce false negatives.
5. Put an exact store behind it
On a negative query, skip an exact lookup only when the filter contains every authoritative key relevant to the request. On a positive query, consult the exact store. Keep updates ordered and synchronized; a stale filter can miss newly added records even though the filter algorithm itself has no false negatives for inserted keys.
Choose an exact hash set when you need exact membership and can afford storing keys. Choose an EGH or Bloom filter for compact negative screening. Compare memory and observed false positives under your real workload before choosing; this tutorial does not claim EGH is universally faster or smaller.
See the native EGH implementation for sizing and hashing details.