.png){kind=icon}
.png){kind=icon}
Return
Efficient Collaborative Data Cleaning Using Private Set Intersection and Encoding for Unbalanced Datasets
.png){kind=icon}
PRE
AI
DOI：10.1109/TIFS.2025.3594871.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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, named uECDC. uECDC employs oblivious key-value stores for slice matching, achieving: 1) a reduction of 18% <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\thicksim ~85$ </tex-math></inline-formula>% in offline phase runtime, and 2) a reduction of 8% <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\thicksim ~43$ </tex-math></inline-formula>% in online phase runtime (under large-scale data settings on the server side), when compared to the slice-linking approach of uPSI-CA. Moreover, we encode server-side data for fast localization of intersection data in unbalanced settings. Under the semi-honest adversary model, uECDC is provably secure. Implementation in Python and C++ demonstrates that uECDC is practically feasible.
Keywords:
Collaborative data cleaning
private set intersection
oblivious key-value stores
unbalanced dataset
privacy protection
Journal
IF:
8
Papers:
5.2K
Citations:
2.3W
View more organizations