UDPLDP-Tree: Range Queries Under User-Distinguished Personalized Local Differential Privacy

Local Differential Privacy (LDP) and its personalized variants (PLDP) have been widely used for privacy-preserving data analytics. However, existing schemes often enforce a uniform indistinguishability level among users, failing to accommodate the nuanced privacy needs of diverse individuals. To address this, we propose User-Distinguished Local Differential Privacy (UDPLDP), a novel framework that formalizes user-level distinguishability to support more flexible, non-uniform privacy budgets. Under this framework, we tackle the fundamental task of frequency range queries, namely UDPLDP-Tree, which overcomes the challenge due to limited user-level distinguishability, insufficient robustness in estimation under complex data distributions, and the assumption of uniform privacy requirements across different attributes in existing multi-dimensional schemes. To demonstrate the effectiveness, we conduct extensive experiments and the results show that UDPLDP-Tree reduces the mean squared error (MSE) by about 30–50% compared with a recent state-of-the-art baseline.