SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics

Alexey Kroshnin; Alexandra Suvorikova

cs.LGFeb 21, 2026

SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics

Authors: Alexey Kroshnin, Alexandra Suvorikova

Organizations: Weierstrass Institute for Applied Analysis and Stochastic

Abstract

Density-adaptive domain discretization is essential for high-utility privacy-preserving analytics but remains challenging under Local Differential Privacy (LDP) due to the privacy-budget costs associated with iterative refinement. We propose a novel framework, Semi-Local Differential Privacy (SLDP), that assigns a privacy region to each user based on local density and defines adjacency by the potential movement of a point within its privacy region. We present an interactive $(\varepsilon, δ)$ -SLDP protocol, orchestrated by an honest-but-curious server over a public channel, to estimate these regions privately. Crucially, our framework decouples the privacy cost from the number of refinement iterations, allowing for high-resolution grids without additional privacy budget cost. We experimentally demonstrate the framework's effectiveness on estimation tasks across synthetic and real-world datasets.

Figures & tables

Figure 1: SLDP function-value release ( $N=3\cdot 10^{4}$ points). From left to right: the private data-adaptive quadtree partition $\hat{\mathcal{F}}_{\mathcal{P}}(\mathbf{X})$ produced by SLDP (left); ground-truth signal $f(x)=\exp(-\|x\|^{2}/(2\sigma^{2}))$ evaluated at the samples; noisy function-value reports under our SLDP with total privacy budget $\varepsilon=1.0$ (and $\delta=0.05$ for SLDP); standard LDP with $\varepsilon=1.0$ .

Panel of Figure 2 — Figure 2: Mean estimation performance under privacy. (a) Convergence comparison for Centralized DP, standard LDP, and SLDP. (b) Error distributions across $N$ and $\varepsilon$ .

Panel of Figure 3 — Figure 3: Classification utility (F1-Score) on the California Housing dataset. Comparison of predictive performance across Random Forest, k-NN, and Logistic Regression classifiers trained on data perturbed by SLDP (Ours), Standard LDP, and Geo-Indistinguishability mechanisms. Results are averaged over 60 independent runs with varying privacy budgets $\varepsilon\in[0.1,10]$ . Shaded areas indicate the standard deviation.

Figure 4: Accuracy of spatial range queries on real-world datasets. Mean Relative Error (MRE) vs. privacy budget ( $\varepsilon$ ) for Brightkite, Geolife, Gowalla, and Porto Taxi datasets for ( $N\in\{5\cdot 10^{3},20\cdot 10^{3}\}$ ).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: The plot illustrates the binary classification task: predicting whether a house value is above (red, Class 1) or below (blue, Class 0) the global median based on geospatial coordinates ( $X_{i}\in[0,1]^{2}$ ).

Figure 6: Hyperparameter sensitivity analysis in SLDP. Hyperparameter sensitivity analysis in SLDP. Distribution of Precision and Recall of a Random Forest classifier trained on SLDP-perturbed data ( $\varepsilon=1.0$ ) as a function of the minimum number of neighbors $k$ required per privacy region.

Figure 7: Visualization of the four real-world geospatial datasets. Each subplot displays a sample of $N=20,000$ data points from Gowalla, Brightkite, Geolife, and Porto Taxi, overlaid with representative spatial range queries (green boxes) generated by the anchored multi-scale strategy.

Figure 8: Data come from a Gaussian mixture. Rectangles correspond to spatial queries.

Figure 9: Accuracy Analysis. Evaluation of the reconstruction error (MRE) on synthetic datasets. Columns correspond to increasing dataset sizes $N$ .

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 276 papers

ABC: Numerical Data Collection under Local Differential Privacy without Prior Knowledge
Aug 6, 2026Incheol Baek, Hyungbin Kim, Yon Dohn ChungDifferential Privacy
Computer Science and Engineering Korea University Seoul, Republic of Korea
Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacy
May 16, 2026Youngmok Ha, Viktor Schlegel, Yidan Sun +1Privacy-Preserving ML Differential Privacy
Department of Bioengineering, Imperial College London, United Kingdom · Artificial Intelligence Computing Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), Daejeon, Republic of Korea · Imperial Global Singapore, Imperial College London, Singapore +1
LDP-Slicing: Local Differential Privacy for Images via Randomized Bit-Plane Slicing
Mar 4, 2026Yuanming Cao, Chengqi Li, Wenbo HePrivacy-Preserving ML Differential Privacy
McMaster University, Hamilton, Ontario, Canada

Aug 6, 2026J/K move · Enter open · S save

ABC: Numerical Data Collection under Local Differential Privacy without Prior Knowledge

Incheol Baek, Hyungbin Kim, Yon Dohn Chung

Computer Science and Engineering Korea University Seoul, Republic of Korea

Differential Privacy

Open paper AskPDF arXiv

Local Differential Privacy (LDP) provides strong privacy guarantees for collecting numerical data. A fundamental challenge, however, is that existing LDP mechanisms require a predefined data domain, which is often unknown in practice. This lack of prior knowledge creates a critical dilemma for the data collector: if the chosen domain is too narrow, values outside the range are clipped, leading to information loss. Conversely, if the domain is too wide, excessive noise is added during the privatization process, which degrades the quality of collected data. This highlights the need for methods that can dynamically estimate the data domain. In this work, we propose an adaptive LDP framework that addresses this problem. In our method, each user sends two pieces of information: their perturbed numerical data, and a privatized signal indicating if their original value was clipped by the current domain. By aggregating these signals, our proposed method, Adaptive Bounding of Clipping regions (ABC) method, iteratively adjusts the domain to fit the underlying data distribution without prior knowledge. Our theoretical analysis shows that the estimated data domain converges to an appropriate range. In the empirical evaluation, the results demonstrate that our framework significantly improves the quality of numerical data collection across various datasets and underlying LDP mechanisms. We also show that the estimated range successfully converges in practice and our approach is robust to its hyperparameters through comprehensive ablation studies.

Abstract

Differential Privacy

Explore similar work

ABC: Numerical Data Collection under Local Differential Privacy without Prior Knowledge

Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacy

LDP-Slicing: Local Differential Privacy for Images via Randomized Bit-Plane Slicing