Bloom Filter

A Bloom filter can definitively state that an element is NOT in a set. This is its most powerful property for fraud detection. When checking if a credit card has been seen before, a negative result is 100% accurate—the card is genuinely new. This eliminates unnecessary database lookups for the vast majority of legitimate transactions, dramatically reducing latency in the authorization flow. The structure never produces false negatives, only false positives.

The probability of a false positive—incorrectly reporting an element is present—is tunable based on three parameters:

• m: The size of the bit array in bits
• k: The number of independent hash functions used
• n: The expected number of elements to be inserted

By adjusting these parameters, engineers can design a filter with a false positive rate as low as 0.001% for critical applications or accept a higher rate to minimize memory usage in less sensitive contexts.

Both insertion and query operations execute in O(k) time complexity, where k is the number of hash functions—a small constant independent of the number of elements stored. This means a Bloom filter with 10 million entries performs queries just as fast as one with 100 entries. For real-time fraud scoring pipelines operating under strict P99 latency budgets, this predictable performance is essential for maintaining sub-millisecond decision times during payment authorization.

A Bloom filter requires significantly less memory than storing the actual elements. For example, storing 1 million credit card numbers with a 1% false positive rate requires approximately 1.14 MB—compared to potentially 16+ MB for the raw data. This compact representation allows fraud detection systems to cache massive sets of known compromised cards, velocity check counters, or blocked device fingerprints entirely in RAM, avoiding expensive disk I/O during the hot path of transaction processing.

Standard Bloom filters do not support element deletion. Because multiple elements can set the same bit positions, clearing a bit to remove one element could inadvertently remove others, causing false negatives. For fraud detection use cases requiring deletion—such as expiring old velocity check windows—engineers use variants like:

• Counting Bloom Filters: Replace bits with small counters, enabling decrement operations
• Sliding Bloom Filters: Maintain multiple time-partitioned filters that are periodically discarded
• Stable Bloom Filters: Continuously evict stale elements by randomly clearing bits

Bloom filters with identical parameters (same m and k) support set union via bitwise OR across their bit arrays. This enables distributed fraud detection architectures where multiple edge nodes maintain local filters of suspicious entities and periodically merge them into a global view without transmitting raw data. Intersection via bitwise AND is theoretically possible but produces a filter with higher false positive rates, making it less reliable for production use in financial systems requiring deterministic accuracy.

A probabilistic sub-linear space data structure used to estimate the frequency of events in a data stream. Unlike a Bloom filter which tests set membership, Count-Min Sketch answers how many times an item has appeared.

• Uses multiple hash functions and a 2D array of counters
• Provides one-sided error: estimates are always ≥ true count
• Ideal for identifying heavy hitters in transaction velocity checks
• Memory footprint remains constant regardless of stream size

In fraud pipelines, Count-Min Sketch efficiently tracks how often a card or IP appears within a sliding window without storing every event.

A rate-limiting algorithm that controls throughput using a fixed-capacity bucket refilled with tokens at a constant rate. Each request consumes one token; if the bucket is empty, the request is rejected or delayed.

• Allows short bursts of traffic up to bucket capacity
• Enforces a long-term average rate via token refill speed
• Smooths out traffic spikes without harsh cutoff thresholds
• Commonly applied to API rate limiting and transaction throttling

In fraud scoring, token buckets prevent brute-force card testing attacks by limiting the number of authorization attempts per card or IP per second.

A continuous computation technique that calculates metrics over a dynamically updating, overlapping time interval. As time advances, the window slides forward, discarding old data and incorporating new events.

• Tumbling windows: fixed, non-overlapping intervals
• Hopping windows: overlapping windows with a defined advance step
• Session windows: dynamic boundaries based on activity gaps
• Critical for computing rolling statistics like transaction count per card in the last 5 minutes

Velocity checks rely on sliding windows to detect anomalous bursts—such as 15 transactions from one device in 60 seconds—that signal card testing or enumeration attacks.

A probabilistic cardinality estimator that counts the number of distinct elements in a multiset using significantly less memory than exact methods. HyperLogLog achieves high accuracy with a typical error rate of only 2%.

• Uses stochastic averaging of hash value bit patterns
• Memory usage is fixed regardless of set size (typically ~1.5 KB)
• Ideal for counting unique visitors, distinct IPs, or unique cards
• Not suitable for membership queries—use a Bloom filter instead

In fraud analytics, HyperLogLog efficiently estimates the number of distinct devices accessing an account or the unique merchants a card has visited, flagging anomalous diversity patterns.

A probabilistic data structure that improves upon the classic Bloom filter by supporting deletion of elements and achieving better space efficiency for low false positive rates. It uses cuckoo hashing to store fingerprints of items.

• Supports dynamic insertions and deletions
• Outperforms Bloom filters when target false positive rate is < 3%
• Stores compact fingerprints rather than setting bits
• Enables set membership testing with item removal capability

Cuckoo filters are valuable in fraud systems where blocklists or watchlists must be updated dynamically—adding and removing compromised cards or flagged devices without rebuilding the entire filter.

An operation that enriches a real-time event stream by joining it with a reference table or materialized view stored in a state store. Each incoming transaction is matched against a lookup table to append contextual data.

• Joins a dynamic stream with a relatively static table
• Enables real-time data enrichment without external service calls
• Uses primary key lookups for millisecond-latency matching
• Example: linking a transaction to merchant risk category or card BIN metadata

In fraud scoring pipelines, stream-table joins combine raw transaction events with Bloom filter membership results, device fingerprints, and historical risk profiles before passing enriched records to the scoring engine.