Online estimation of robust statistics, namely quantiles, is of great interest in several applications where high-rate data streams must be processed as quickly as possible and discarded, being their storage usually unfeasible. Fast and accurate estimation is challenging when considering the additional constraint of differential privacy, which leads to the well-known privacy-utility trade-off. Recent approaches further require the use of a minimal amount of space (even a single memory variable), so as to reduce the complexity. In this paper we present three differentially-private streaming algorithms for frugal estimation of a quantile, based on different modifications of the Frugal-1U algorithm: DP-Frugal-1U-L, DP-Frugal-1U-G, and DP-Frugal-1U-ρ. We specifically provide a theoretical analysis and experimental results.
Space-Efficient Private Estimation of Quantiles
Cafaro M.;Coluccia A.;Epicoco I.;Pulimeno M.
2025-01-01
Abstract
Online estimation of robust statistics, namely quantiles, is of great interest in several applications where high-rate data streams must be processed as quickly as possible and discarded, being their storage usually unfeasible. Fast and accurate estimation is challenging when considering the additional constraint of differential privacy, which leads to the well-known privacy-utility trade-off. Recent approaches further require the use of a minimal amount of space (even a single memory variable), so as to reduce the complexity. In this paper we present three differentially-private streaming algorithms for frugal estimation of a quantile, based on different modifications of the Frugal-1U algorithm: DP-Frugal-1U-L, DP-Frugal-1U-G, and DP-Frugal-1U-ρ. We specifically provide a theoretical analysis and experimental results.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
