SparseBF: Enhancing Scalability and Efficiency for Sparsely Filled Privacy-Preserving Record Linkage

Bloom filter (BF) encodings are a proven method for comparing the similarity of records from multiple databases while maintaining privacy. This process, known as privacy-preserving record linkage (PPRL), is computationally expensive, especially with large datasets. To address this challenge, we have observed that BF encodings often exhibit sparsely filled patterns. Leveraging this insight, we introduce SparseBF, a scalable data structure that is space-optimized and maintains fast computation speed for PPRL. Compared to typical BF encodings, SparseBF brings in three improvements. First, SparseBF employs a hybrid storage scheme that selects the optimal storage component for BF encodings. Second, SparseBF utilizes its adaptive compressed sparse row storage to achieve lossless space compression, both when BFs are sparsely occupied and when they are densely populated. Third, SparseBF supports SIMD vector instructions to optimize the record linkage speed. Experiments show that, in sparsely filled scenarios, SparseBF outperforms the existing solution by up to 2.1x record linkage computation speed, while delivering up to 70.5% savings in storage space.