Ternary Bloom Filters: An Exploration of Uncertainty, Optimization, and Tuning

In traditional Bloom filters, membership is a binary decision: an element is either “possibly in” or “definitely not in” the set. But what if we could go a step further? What if, in addition to “true” and “false,” we had a state for “maybe” that explicitly captures uncertainty?

In this post, we dive into the design and tuning of a ternary Bloom filter that returns true, false, or maybe for each cell. We also explore a multi-layer approach, feature-level tweaking with hash salts, and an optimization strategy by iteratively shrinking the filter size.

Overview of the Ternary Bloom Filter

A ternary Bloom filter extends the conventional Bloom filter by introducing a third state—maybe—to indicate ambiguous or conflicting evidence. Each cell (or trit) in the filter can be:

• True: Clear evidence that an element is in the set.
• False: Clear evidence that an element is not in the set.
• Maybe: Ambiguous or conflicting signals where the evidence for both true and false exists.

The aim is to provide a probabilistic data structure that not only hints at membership but also quantifies uncertainty. This design is especially useful in scenarios where data can be noisy or when the cost of false positives and negatives is asymmetric.

The Two-Layer Approach: Global and Local Filters

To further enhance the control over uncertainty, we propose a two-layer design:

1. Global Filter:
   This filter represents the overall state across all features. Each cell in the global filter is assigned a value based on the aggregated evidence from multiple features. Initially, these cells are set to the “true” or “false” values as determined by the combined feature signals.

2. Local Filter:
   Each feature has its own local filter that can be tuned individually. All local filter cells start as maybe (i.e., a 100% maybe rate) and are later refined based on evidence coming from the feature’s dedicated hash functions.

This separation enables us to fine-tune the influence of individual features while still maintaining a robust global consensus.

Greedy Resolution to Meet the Maybe Rate

The maybe rate—the proportion of cells with ambiguous results—is a critical parameter. We want to meet a specific maybe rate requirement while resolving cells with unambiguous evidence. The following steps outline a greedy resolution process:

1. Global Initialization:
   Set each global cell based on the aggregated true/false counts from all features.

2. Local Initialization:
   Set all local cells initially to maybe.

3. Greedy Update:
   For each local cell that is still maybe, check if there is unambiguous evidence:

   • If a cell has some true signals and zero false signals, set it to true.
   • If a cell has some false signals and zero true signals, set it to false.

This process reduces the maybe rate while preserving ambiguity where conflicting evidence exists.

Ternary Logic Functions: Exploring the Options

When aggregating true, false, and maybe values, different logic functions can be employed. Below is a table summarizing some potential approaches:

In mathematical terms, consider a cell where the counts are given by \( T \) for true and \( F \) for false. A simple majority function could be expressed as:

$$ \text{Result} = \begin{cases} \text{true}, & \text{if } T > F \ \text{false}, & \text{if } F > T \ \text{maybe}, & \text{if } T = F \end{cases} $$

Alternatively, a threshold-based decision function might resolve to true if:

$$ \frac{T}{T + F} > \theta $$

and to false if:

$$ \frac{F}{T + F} > \theta, $$

with \(\theta\) being a configurable parameter that allows for fine-tuning the resolution.

Tweaking with Hash Salts and Filter Size

Feature-Level Tweaking with Hash Salts

Each feature in our ternary Bloom filter can be tweaked by controlling the hash salt used during the hashing process. This gives you the ability to:

• Adjust Distribution: A specific salt can help ensure that features are distributed more evenly across the filter, reducing clustering.
• Control Influence: Some features may need a stronger or weaker influence on the resolution process. Tweaking the salt allows for this per-feature control.

Global Tuning by Reducing Filter Size

Initially, our ternary Bloom filter can be extremely large so that features hash to almost entirely distinct cells. This results in a trivially low maybe rate because each feature’s influence remains isolated. However, a large filter might be inefficient. Therefore, we can iteratively reduce the filter size using a modulo operation.

The Process

1. Start Large:
   With a very large filter, each feature almost certainly occupies a unique cell, leading to a low maybe rate.

2. Shrink Iteratively:
   Reduce the filter size by one trit cell at a time (or by a fixed decrement). Mathematically, if the original cell index is \( i \), the new index might be computed as:

   $$ i_{\text{new}} = i \mod N, $$

   where \( N \) is the new (smaller) filter size.

3. Backtesting:
   After each reduction, backtest the overall maybe rate by processing the same set of features and measuring the proportion of maybe cells. If the maybe rate remains within the acceptable threshold, the new size is valid; if not, adjustments can be made.

Conclusion

The ternary Bloom filter represents an innovative step ahead over traditional binary Bloom filters by explicitly incorporating uncertainty. With careful calibration—using techniques such as majority-based, threshold-based, or weighted voting functions—developers can create robust probabilistic data structures that are both space-efficient and expressive.

Whether you’re tackling noisy data or designing systems with asymmetric error costs, the ternary Bloom filter offers a flexible and innovative solution worth exploring further.