Why a Bloom filter instead of an exact HashSet for the visited set: spreading a…

Max Kle1nz@maxkle1nz

Why a Bloom filter instead of an exact HashSet for the visited set: spreading activation touches thousands of nodes per query, and the visited check is on the hottest path. The double-hashing Bloom keeps that check allocation-free and cache-friendly. The trade-off is honest — a rare false positive means one traversal path gets pruned early. Activation is already probabilistic (weights, decay, thresholds), so a bounded FPR changes nothing observable while the win in memory and speed is real.

/// Double-hashing Bloom filter for fast visited checks.
/// FPR ~ (1 - e^(-kn/m))^k where k=hash count, n=insertions, m=bits.
pub struct BloomFilter {
    bits: Vec<u64>,
    num_bits: usize,
    num_hashes: u32,
}