Bloom Filter Encoding

A Bloom filter is a probabilistic data structure that represents a set of elements using a fixed-size bit array and k independent hash functions. When an attribute like a surname is inserted, each hash function maps it to a position in the bit array, setting those bits to 1.

• Space complexity: O(m) where m is the bit array size, regardless of element count
• False positive rate is tunable based on array size and hash function count
• No false negatives: if an element was inserted, the query will always return true
• Typical configurations use 500–1000 bits per record for name encoding

The compact representation allows entire identity databases to be encoded in memory, making it ideal for high-throughput privacy-preserving record linkage pipelines.

Once an attribute is encoded into a Bloom filter, the original plaintext value cannot be recovered from the bit array. This cryptographic property makes Bloom filters ideal for privacy-preserving applications where personally identifiable information must be protected.

• Multiple hash functions create a many-to-one mapping that destroys reversibility
• Bits set to 1 could originate from any of several possible input values
• Provides computational irreversibility without requiring full encryption
• Compliant with data minimization principles under GDPR and similar regulations

This one-way property enables organizations to share encoded identity tokens for linkage without exposing raw PII, satisfying both operational and regulatory requirements.

Bloom filters naturally support approximate string matching through set-based similarity measures. The Dice coefficient calculates the overlap between two bit arrays, providing a similarity score between 0 and 1.

• Dice(A,B) = 2 × |A ∩ B| / (|A| + |B|), where |X| is the count of set bits
• Typographical errors produce only minor bit differences in the encoded output
• A threshold of 0.75–0.85 typically indicates a probable match for names
• Outperforms exact matching when dealing with data entry errors, transliteration variants, and nicknames

This enables linkage of records like "Jon Smith" and "John Smyth" without ever decrypting or exposing the original strings, combining privacy with practical matching tolerance.

Before hashing into the Bloom filter, input strings are decomposed into q-grams—overlapping substrings of length q. This tokenization step is what gives Bloom filter encoding its resilience to character-level variations.

• Bigrams (q=2): "SMITH" → {S, SM, MI, IT, TH, H}
• Trigrams (q=3): "SMITH" → {SM, SMI, MIT, ITH, TH}
• Padding characters (typically underscore) mark string boundaries
• Each q-gram is independently hashed into the Bloom filter
• Longer q values increase precision; shorter q values increase recall

The q-gram approach ensures that a single character substitution, deletion, or insertion affects only a limited number of bit positions, preserving overall similarity for fuzzy matching.

Real-world identity resolution requires matching on multiple attributes simultaneously. Bloom filters support composite encoding where several identity fields are combined into a single bit array.

• Each attribute (first name, last name, DOB, address) is independently tokenized
• A field-specific salt or prefix is added to prevent cross-attribute collisions
• All q-grams from all attributes are hashed into the same bit array
• Similarity comparison operates on the unified encoding
• Weighted variants can assign different bit allocations per attribute based on discriminatory power

This approach enables holistic identity comparison in a single operation, dramatically reducing computational complexity compared to pairwise attribute matching.

Bloom filter encoding is the foundational technology behind privacy-preserving record linkage (PPRL) protocols, enabling organizations to identify matching records across databases without sharing raw PII.

• Encoding phase: Each party independently encodes their identity attributes into Bloom filters
• Exchange phase: Only the irreversible bit arrays are transmitted
• Comparison phase: Dice coefficient or Jaccard similarity is computed on the encoded values
• Linkage phase: Pairs exceeding the similarity threshold are flagged as potential matches
• No trusted third party is required; the protocol works in bilateral and multilateral configurations

This architecture is widely deployed in healthcare research networks, financial crime consortia, and national statistical agencies where data sharing is legally constrained.

The overarching cryptographic framework that enables matching records across databases without exposing plaintext personally identifiable information (PII). Bloom filter encoding serves as one of the primary encoding strategies within PPRL protocols, alongside secure multi-party computation and homomorphic encryption. The goal is to compute similarity scores on encoded data such that the output reveals only matching record pairs, not the underlying attributes.

A string comparison technique that calculates the probability of two text strings referring to the same entity despite typographical errors, abbreviations, and formatting inconsistencies. When attributes like names or addresses are Bloom-encoded, fuzzy matching is performed on the bit arrays using set-based similarity metrics rather than edit-distance algorithms, enabling privacy-preserving approximate string matching.

A performance optimization that partitions large datasets into mutually exclusive blocks using common attributes before comparison. In Bloom filter PPRL, blocking keys are often derived from encoded phonetic representations or n-gram subsets to group candidate pairs, reducing the quadratic comparison problem to manageable sub-problems without compromising privacy guarantees.

A set-based similarity metric defined as twice the intersection size divided by the sum of the sizes of two sets. For Bloom filter comparison, the Dice coefficient is computed on the bit positions set to 1, providing a robust measure of overlap that is resilient to the probabilistic nature of Bloom filters and more appropriate than exact match comparisons.

The preprocessing step that decomposes attribute strings into overlapping substrings of length n before encoding. For example, 'smith' yields bigrams: s, sm, mi, it, th, h. Each n-gram is hashed into the Bloom filter, enabling fuzzy matching because small typographical changes affect only a subset of n-grams, preserving partial bit pattern similarity.

The foundational probabilistic record linkage framework that classifies record pairs as matches, non-matches, or potential matches based on agreement pattern likelihood ratios. When combined with Bloom filter encoding, the Fellegi-Sunter model operates on similarity scores derived from bit array comparisons rather than raw attribute agreements, maintaining statistical rigor in privacy-preserving contexts.