(ϵ, δ)-Local differential privacy mechanism for set-valued data analysis

(ϵ, δ)-Local Differential Privacy ((ϵ, δ)-LDP) ensures rigorous privacy protection for individual users without requiring trusted data aggregator, while enabling accurate statistical analysis of privatized data. Multiple (ϵ, δ)-LDP mechanisms have been developed to deal with data analysis tasks including frequency estimation of categorical data and mean estimation of numeric data. However, the (ϵ, δ)-LDP mechanism for set-valued data analysis has yet to be established.
To this end, a research team led by Bing CHEN focused on (ϵ, δ)-LDP mechanism under the task of frequency estimation over set-valued data and published their new research on 15 June 2026 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team proposed two novel (ϵ, δ)-LDP mechanisms, PrivSet-ALDP and Wheel-ALDP, to support frequency estimation task over set-valued data. In proposed schemes, each user has set-valued data containing multiple items and independently perturbs their set-valued data through PrivSet-ALDP mechanism or Wheel-ALDP mechanism. Then, each user reports the perturbed data instead of raw data to the data aggregator. Finally, the data aggregator estimates the item distribution based on all collected perturbed data.
In the research, they theoretically prove that the proposed mechanisms provide (ϵ, δ)-LDP for each user and conduct experiments on synthetic datasets to compare the proposed mechanisms with the random-sampling based approaches and illustrate their effectiveness. Experimental results demonstrate the PrivSet-ALDP and Wheel-ALDP mechanisms achieve better utility.
For the future direction, one is to design set-valued data analysis (ϵ, δ)-LDP mechanisms with tighter error bounds and higher data utility. Another is to propose a (ϵ, δ)-LDP mechanism to support key-value data analysis task.