Differentially private range counting: where asymptotically better fails, integer covering prevails

Abstract This work addresses the problem of maintaining privacy in range counting queries, with a focus on rolling-window queries over sensitive data. By employing differential privacy (DP), we can protect sensitive data used in these queries, as demonstrated in applications like COVID-19 tracking. Our research, however, identifies significant limitations in existing DP methods for small to medium-sized windows or ranges, which are commonly found in practical applications. We introduce a novel combinatorial interval covering approach, providing a detailed analysis of privacy-utility trade-offs within the DP framework. Our characterization of interval covering families’ thickness provides new insights into achieving $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -DP with minimal error. Additionally, we propose a search-based method for selecting optimal families for differentially private range counting queries, specifically for small to medium windows, which outperforms current solutions in relevant scenarios. This work contributes to both the theoretical foundation and practical application of differential privacy in data analytics, ensuring robust privacy protection without compromising query accuracy.