Efficient Collaborative Data Cleaning Using Private Set Intersection and Encoding for Unbalanced Datasets
Jingting Xue, Wenyi Li, Fagen Li, Wenzheng Zhang, Yu Zhou, Xiaojun Zhang · IEEE Transactions on Information Forensics and Security · 2025
Data cleaning improves quality and consistency by detecting, localizing, and repairing “dirty” data without compromising sensitive information. Collaborative Data Cleaning employs a distributed model to avoid single points of failure and trust issues in centralized systems, although it incurs additional communication overhead. Blass et al. (S&P’23) were the first to implement CDC via balanced Private Set Intersection (PSI). Unbalanced PSI (e.g.,uPSI-CA, USENIX’23) does not address the localization of intersections within datasets and thus cannot be directly applied to CDC. uPSI-based data cleaning remains largely unexplored. In this paper, we propose an efficient CDC scheme for unbalanced datasets, nameduECDC.uECDCemploys oblivious key-value stores for slice matching, achieving: i) a reduction of 18% ~ 85% in offline phase runtime, and ii) a reduction of 8% ~ 43% in online phase runtime (under large-scale data settings on the server side), when compared to the slice-linking approach ofuPSI-CA. Moreover, we encode server-side data for fast localization of intersection data in unbalanced settings. Under the semi-honest adversary model,uECDCis provably secure. Implementation in Python and C++ demonstrates thatuECDCis practically feasible.