Scalable privacy-preserving record linkage: Evaluating MultiBit tree indexing in Atyimo - Orrico, Victor; Eustáquio, Fernanda; Almeida, Bethânia; Silva, Mirlei; Pita, Robespierre (Anais do Simpósio Brasileiro de Banco de Dados (SBBD); 2025: Anais do XL Simpósio Brasileiro de Bancos de Dados, 2025)
Privacy-preserving record linkage (PPRL) indexing techniques typically organize Bloom Filters (BF) into data structures to reduce unnecessary comparisons. However, widely used solutions like Multibit Trees (MTB) often face scalability issues with large datasets or high-dimensional BFs, requiring parallel or distributed computation. This study explores the integration of the MTB algorithm into Atyimo, a publicly available Brazilian PPRL tool for merging large-scale administrative databases. We used both simulated and real-world data in our experiments to evaluate Atyimo’s effectiveness with MTB in linking routinely collected health records in Brazil. The results show that our Spark DataFrame-based solution builds robust index structures that preserve the linkage accuracy and significantly reduce execution time compared to the baseline.